CodeForces - 1250J The Parade 二分

题意：

一共n种身高，每一个士兵有一个身高。你需要把他们安排成k行(士兵不需要全部安排)，每一行士兵身高差距小于等于1.你要找出来最多能安排多少士兵

题解：

这道题很容易就能看出来就是一道二分，二分一行有多少士兵(假设二分出来的值为x)

因为题目上说明每一行士兵的身高差距不能大于1，所以只有输入这n个身高中相邻的才可以安排在一行

TLE代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<queue>

 6 using namespace std;

 7 const int maxn=30005;

 8 const int INF=0x3f3f3f3f;

 9 typedef long long ll;

10 ll v[maxn],n,k,w[maxn];

11 bool panduan(ll x)

12 {

13     for(ll i=1;i<=n;++i)

14         w[i]=v[i];

15     ll start=1,ci=k;

16     while(ci)

17     {

18         if(w[start]>=x)

19         {

20             w[start]-=x;  //因为我这里是一次一次减x，所以会超时

21             ci--;

22         }

23         else

24         {

25             if(w[start]+w[start+1]>=x && start+1<=n)

26             {

27                 w[start+1]=(w[start]+w[start+1])-x;

28                 start++;

29                 ci--;

30             }

31             else

32             {

33                 start++;

34             }

35         }

36         if(start>n) break;

37     }

38     if(ci) return 0;

39     else return 1;

40 }

41 int main()

42 {

43     ll t;

44     scanf("%lld",&t);

45     while(t--)

46     {

47         ll sum=0;

48         scanf("%lld%lld",&n,&k);

49         for(ll i=1;i<=n;++i)

50         {

51             scanf("%lld",&v[i]);

52             sum+=v[i];

53         }

54         ll mid,ans=0,l=1,r=sum/k;  //这里一定要给ans初始化为0

55         while(l<=r)

56         {

57             mid=(l+r)>>1;

58             if(panduan(mid))

59             {

60                 ans=mid;

61                 l=mid+1;

62             }

63             else r=mid-1;

64         }

65         printf("%lld\n",ans*k);

66     }

67     return 0;

68 }

正确代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<queue>

 6 using namespace std;

 7 const int maxn=30005;

 8 const int INF=0x3f3f3f3f;

 9 typedef long long ll;

10 ll v[maxn],n,k,w[maxn];

11 bool panduan(ll x)

12 {

13     for(ll i=1; i<=n; ++i)

14         w[i]=v[i];

15     ll start=1,ci=k;

16     while(ci>0)

17     {

18         if(w[start]>=x)

19         {

20             ci=ci-w[start]/x;

21             w[start]%=x;

22         }

23         else

24         {

25             if(start+1<=n && w[start]+w[start+1]>=x)

26             {

27                 ci=ci-(w[start]+w[start+1])/x;

28                 w[start+1]=(w[start]+w[start+1])%x;

29                 start++;

30             }

31             else

32             {

33                 start++;

34             }

35         }

36         if(start>n) break;

37     }

38     if(ci<=0) return 1;

39     else return 0;

40 }

41 int main()

42 {

43     ll t;

44     scanf("%lld",&t);

45     while(t--)

46     {

47         ll sum=0;

48         scanf("%lld%lld",&n,&k);

49         for(ll i=1;i<=n;++i)

50         {

51             scanf("%lld",&v[i]);

52             sum+=v[i];

53         }

54         ll mid,ans=0,l=1,r=sum/k;  //一定要给ans初始化为0，我错了好几次。。

55         while(l<=r)

56         {

57

58             mid=(l+r)/2;

59             if(panduan(mid))

60             {

61                 ans=mid;

62                 l=mid+1;

63             }

64             else r=mid-1;

65         }

66         printf("%lld\n",ans*k);

67     }

68     return 0;

69 }

巴特西

CodeForces - 1250J The Parade 二分

最新文章

热门文章