求助一道算法题目
题目如图
这题我觉得最好就是用对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墙这样循环
相关推荐
07-09 13:51
门头沟学院 Java 还处在暑期实习上岸后的摆烂状态实习:杂活多,产出少,文档也没偷学多少八股:忘的差不多了项目:有实习就不会问玩具项目了吧力扣:我可以说我连hot 100都没刷完吗国企:从零开始准备论文:没着落
回收旧报纸:世另我,只是我比你更烂一些,没找到实习,你起码还有实习的,秋招猛猛冲,加油
点赞 评论 收藏
分享
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享