求助一道算法题目
题目如图
这题我觉得最好就是用对k二分来做,但是我总是过不了测试用例,牛客上的那测试用例老长一串又复制不了,有没有大佬帮我看下代码哪里有问题呀?感激不尽!!代码如下:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt(),m=in.nextInt();
TreeSet<Integer> set=new TreeSet<>();
in.nextLine();
String wall=in.nextLine();
for(int i=0;i<n;i++) {
if(wall.charAt(i)=='W') set.add(i);
}
if(set.ceiling(0)==null) System.out.print(0);
int left=-1,right=n+1;
while(left+1<right) {
int mid=(left+right)/2;
if(check(set,mid,m)) right=mid;
else left=mid;
}
System.out.print(right);
}
public static boolean check(TreeSet<Integer> set,int k,int m) {
int idx=set.ceiling(0);
for(int i=0;i<m;i++) {
idx+=k;
if(set.ceiling(idx)==null) return true;
}
return false;
}
}
这题我觉得最好就是用对k二分来做,但是我总是过不了测试用例,牛客上的那测试用例老长一串又复制不了,有没有大佬帮我看下代码哪里有问题呀?感激不尽!!代码如下:
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n=in.nextInt(),m=in.nextInt();
TreeSet<Integer> set=new TreeSet<>();
in.nextLine();
String wall=in.nextLine();
for(int i=0;i<n;i++) {
if(wall.charAt(i)=='W') set.add(i);
}
if(set.ceiling(0)==null) System.out.print(0);
int left=-1,right=n+1;
while(left+1<right) {
int mid=(left+right)/2;
if(check(set,mid,m)) right=mid;
else left=mid;
}
System.out.print(right);
}
public static boolean check(TreeSet<Integer> set,int k,int m) {
int idx=set.ceiling(0);
for(int i=0;i<m;i++) {
idx+=k;
if(set.ceiling(idx)==null) return true;
}
return false;
}
}
全部评论
没有二分性质啊宝贝,其实最左边的w墙一定要被染色的,那我们就染他,染他那么他右边再数k-1个墙就是红色了。然后再找剩下序列最左边的w墙这样循环
相关推荐
09-22 09:42
门头沟学院 Java 牛客37185681...:马德,我感觉这是我面过最恶心的公司,一面是两个女hr,说什么实习前几个月属于试用期,试用期过了才能转成正式实习生,我***笑了,问待遇就是不说,问能不能接受全栈,沙币公司
点赞 评论 收藏
分享
vivo公司福利 369人发布
