Beautiful Dream hdu3418 （直接做或二分）

Beautiful Dream

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 629 Accepted Submission(s): 224

Problem Description

When we were a child, we all had a beautiful dream, time flies, where is your colorful dream living in now?
Get it? If not, it doesn’t matter, today is your lucky day, our kindly angel cast some items, if you get more than m different kind of items, you will get the gift of the angel: help you achieve your childhood dream.
Now we know the number of each item, find the maximum number of people who can achieve their dreams.

Input

There are several test cases in the input.
The first line of each case contains two integer n (0 < n <= 100) and m (0 < m <= n), indicating the items’ kind number and the least different kind number of items you need collect to achieve your dream.
The n integer follows, indicating number of each item, you can assume the range of items’ number is in 1 - 1 000 000 000.
The input terminates by end of file marker.

Output

For each test case, output the maximum number of people who can achieve their dreams.

Sample Input

2 2

3 5

3 2

2 2 2

Sample Output

直接：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 int a[100];
 8 int main()
 9 {
10     int m,n,i;long long ans;
11     while(~scanf("%d%d",&n,&m))
12     {
13         ans=0;
14         for(i=0;i<n;i++)scanf("%d",&a[i]),ans+=a[i];
15         bool flag=1;
16         ans/=m;
17         while(flag)
18         {
19             flag=0;
20             for(i=0;i<n;i++)
21                 if(a[i]>ans)a[i]=ans,flag=1;
22                 ans=0;
23             for(i=0;i<n;i++)ans+=a[i];
24             ans/=m;
25         }
26         printf("%I64d
",ans);
27     }
28 }

View Code

二分：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 long long a[100];
 8 int main()
 9 {
10     int m,n,i;long long ans;
11     while(~scanf("%d%d",&n,&m))
12     {
13         ans=0;
14         for(i=0;i<n;i++)scanf("%I64d",&a[i]),ans+=a[i];
15         long long l=0,r=ans/m,mid;
16         while(l<=r)
17         {
18             mid=(l+r)>>1;
19             ans=0;
20             for(i=0;i<n;i++)ans+=min(a[i],mid);
21             if(ans>=mid*m)l=mid+1;
22             else r=mid-1;
23         }
24         printf("%I64d
",r);
25     }
26 }

View Code