狂牛病&カエルが橋を渡る586
狂牛病
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
4
説明
農夫Johnは、N(2<=N<=100000)個の仕切りを含む長い畜舎を建て、これらの小さな仕切りはx 1の順に番号が付けられています.xN (0 <= xi <= 1,000,000,000).
しかし、ジョンのC(2<=C<=N)頭牛たちはこのようなレイアウトが好きではなく、数頭の牛を1つの仕切りに置くと、争いが起こる.牛同士を傷つけないように.ジョンは自分で牛に仕切りを割り当てて、任意の2頭の牛の間の最小距離をできるだけ大きくすることにした.では、この最大の最小距離は何だろうか.
入力
複数組のテストデータがあり、EOFで終了します.
1行目:スペースで区切られた2つの整数NとC
2行目-N+1行目:xiの位置をそれぞれ指摘
しゅつりょく
テストデータのセットごとに整数を出力し、問題の最大の最小値を満たし、改行に注意します.
サンプル入力
サンプル出力
3
この問題は牛と牛の最大距離の最小値を探すことです.
牛が互いに傷つけないことを保証する方法は彼らの間を隔てなければならなくて、距離は1と仕切りより大きくなければなりません!!!
二分で検索するので、数列は秩序正しくなければならないので、まず数列を並べ替えて処理します.
#include #include using namespace std; #define M 100000 int s[M],n,c;; int f(int x)/このとき伝わる値は牛柵の距離{int niu,t,i;niu=1;t=s[0]//牛を最初の位置に置くfor(i=1;i{if(s[i]-t>=x){t=s[i];niu++;if(niu>=c)//牛が互いに傷つけないように適合した上ですべての牛に場所return 1を持たせる;return 0; } int bsearch()/二分関数、なぜ二分法を使うのですか?
牛と牛の間の距離は、一緒にいるか、最も遠く離れているか、すなわち両端{int l,r,mid;l=0;r=s[n-1]-s[0];while(l<=r){mid=(l+r)/2;if(f(mid)/f関数を満たす上で位置l=mid+1;elser=mid-1;return r; } int main() {int i;while(~scanf("%d%d",&n,&c)){for(i=0;i{scanf("%d",&s[i]);}sort(s,s+n);//ソートを忘れないでください.これは重要なprintf("%d",bsearch();}return 0; }
下はカエルが川を渡る
カエルが橋を渡る
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
3
説明
The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).
入力
The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.
しゅつりょく
For each case, output a integer standing for the frog's ability at least they should have.
サンプル入力
サンプル出力
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
4
説明
農夫Johnは、N(2<=N<=100000)個の仕切りを含む長い畜舎を建て、これらの小さな仕切りはx 1の順に番号が付けられています.xN (0 <= xi <= 1,000,000,000).
しかし、ジョンのC(2<=C<=N)頭牛たちはこのようなレイアウトが好きではなく、数頭の牛を1つの仕切りに置くと、争いが起こる.牛同士を傷つけないように.ジョンは自分で牛に仕切りを割り当てて、任意の2頭の牛の間の最小距離をできるだけ大きくすることにした.では、この最大の最小距離は何だろうか.
入力
複数組のテストデータがあり、EOFで終了します.
1行目:スペースで区切られた2つの整数NとC
2行目-N+1行目:xiの位置をそれぞれ指摘
しゅつりょく
テストデータのセットごとに整数を出力し、問題の最大の最小値を満たし、改行に注意します.
サンプル入力
5 3
1
2
8
4
9サンプル出力
3
この問題は牛と牛の最大距離の最小値を探すことです.
牛が互いに傷つけないことを保証する方法は彼らの間を隔てなければならなくて、距離は1と仕切りより大きくなければなりません!!!
二分で検索するので、数列は秩序正しくなければならないので、まず数列を並べ替えて処理します.
#include #include using namespace std; #define M 100000 int s[M],n,c;; int f(int x)/このとき伝わる値は牛柵の距離{int niu,t,i;niu=1;t=s[0]//牛を最初の位置に置くfor(i=1;i{if(s[i]-t>=x){t=s[i];niu++;if(niu>=c)//牛が互いに傷つけないように適合した上ですべての牛に場所return 1を持たせる;return 0; } int bsearch()/二分関数、なぜ二分法を使うのですか?
牛と牛の間の距離は、一緒にいるか、最も遠く離れているか、すなわち両端{int l,r,mid;l=0;r=s[n-1]-s[0];while(l<=r){mid=(l+r)/2;if(f(mid)/f関数を満たす上で位置l=mid+1;elser=mid-1;return r; } int main() {int i;while(~scanf("%d%d",&n,&c)){for(i=0;i{scanf("%d",&s[i]);}sort(s,s+n);//ソートを忘れないでください.これは重要なprintf("%d",bsearch();}return 0; }
下はカエルが川を渡る
カエルが橋を渡る
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
3
説明
The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).
入力
The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.
しゅつりょく
For each case, output a integer standing for the frog's ability at least they should have.
サンプル入力
6 1 2
2
25 3 3
11
2
18サンプル出力
4
11 ： ？ ， ， ， 6 1 2 1. 6 ， 2 2 ， 4 ； 4 ，#include
#include
using namespace std;
#define MAX 500005
int p[MAX];
int pass(int l,int n,int m,int min)//
{
int s=0,now=0,i;//now ， ，
for(i=0;i<=n;)
{
if(++s>m||p[i]-now>min)// ++s ，m
return 0;
while(p[i]-now<=min&&i<=n)
i++;
now=p[i-1];
}
return 1;
}
int main()
{
int l,n,m,min,max;
int i,mid;
while(scanf("%d%d%d",&l,&n,&m)!=EOF)
{
for(i=0;i {
scanf("%d",&p[i]);
}
p[n]=l;
sort(p,p+n);
min=0;
max=l;
while(min {
mid=(min+max)/2;
if(pass(l,n,m,mid))
max=mid;
else
min=mid+1;
}
printf("%d
",max);
}
return 0;
}