求助一道算法题目
题目如图
这题我觉得最好就是用对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墙这样循环
相关推荐
点赞 评论 收藏
分享
投票

点赞 评论 收藏
分享
点赞 评论 收藏
分享