A-Aggressive cows POJ-2456(二分特集)
919 ワード
https://vjudge.net/contest/241402#problem/A
タイトル:
n個の牛の柵があって、m個を選んで牛に入れて、1本の線分の上でn個の点があることに相当して、m個の点を選んで、隣接する点の間の最小距離の値が最大になるようにします
考え方:隣接する2つの牛の間隔を2分列挙し、この間隔以上ですべての牛を入れることができるかどうかを判断する.具体的にはコードを参照.
タイトル:
n個の牛の柵があって、m個を選んで牛に入れて、1本の線分の上でn個の点があることに相当して、m個の点を選んで、隣接する点の間の最小距離の値が最大になるようにします
考え方:隣接する2つの牛の間隔を2分列挙し、この間隔以上ですべての牛を入れることができるかどうかを判断する.具体的にはコードを参照.
#include
#include
#include
using namespace std;
int n,c,a[100005];
int judge(int x) // x ,
{
int i,s=1,p=a[0]; // a[0]
for(i=1; i=x)
{
s++;//s
p=a[i]; //p
}
}
return s;
}
int main()
{
int i,j;
scanf("%d%d",&n,&c);
for(i=0; i=low)
{
mid=(low+high)/2;
if(judge(mid)>=c) // >=c , ,
low=mid+1;
else // , 。
high=mid-1;
}
printf("%d
",mid);
return 0;
}