poj2456 Aggressive cows 二分我怎么这么弱

答案:2 悬赏:0 手机版

解决时间 2021-02-26 20:04

提问者网友：几叶到寒
2021-02-26 15:57

最佳答案

五星知识达人网友：平生事
2021-02-26 16:02

#include
#include
#include

using namespace std;

const int maxn=100010;

int n,k;
int dis[maxn];

//读入优化,就可以比别人速度快了2333
inline int in(){
int x=0;char ch=getchar();
while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}

//二分距离后贪心判定
bool judge(int Min){
//last表示上一只牛的位置,cnt表示已经放下牛的个数
int last=dis[1],cnt=1;
for(int i=2;i<=n;i++)

if(dis[i]-last>=Min){
cnt++,last=dis[i];
if(cnt>=k) return true;//如果放下了k头牛,就可以返回了.
}
return false;
}

int main(){
#ifndef ONLINE_JUDGE
freopen("x.in","r",stdin);
freopen("x.out","w",stdout);
#endif

n=in(),k=in();
for(int i=1;i<=n;i++) dis[i]=in();
//注意要先将牛栏排序
sort(dis+1,dis+n+1);

//l,r表示可以放的距离的上下界.一般怕错的话,就不设为0和dis[n],不然比如答案=dis[n]时如果r=dis[n]就有问题了...虽然我下面那个地方还是做了这个判断...
//其实还有优化,就是最后的答案一定是某两个位置的差值,你只要从差值的数据中二分就可以了.不过一个是log2(1e9)一个是log2(1e5)感觉也差不多...
int l=0,r=dis[n]+1,mid;
//终止条件是这个区间的长度为2,如果为2了不终止,很有可能就会mid=(l+r)>>1=l,l=mid,然后不停的循环下去然后TLE,如果>2的话mid!=l.
while(r-l>1){
mid=(l+r)>>1;
if(judge(mid)) l=mid;
else r=mid;
}
//结束之后还有两个元素一个l一个r,因为l是一定满足的[每次等于了judge(mid)=1的mid],所以可以再判一下r,如果符合就选r
if(judge(r)) l=r;
printf("%d",l);

return 0;
}
//这个程序在poj上已经通过了所有的测试点
//15634063 Robert_Yuan 2456 Accepted 520K 266MS C++ 1242B 2016-06-24 20:26:53

...这里回答竟然找不到那个代码框了QAQ...你试着复制一下再去看吧...文本格式一定丑飞了...

上面的回答是回答这道题的二分解法的...
如果你问的是"我怎么这么弱"的话...我也没办法了...因为我也这么弱QAQ

全部回答

1楼网友：时间的尘埃
2021-02-26 16:22

相信自己的判断吧

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

poj2456 Aggressive cows 二分 我怎么这么弱

poj2456 Aggressive cows 二分我怎么这么弱