[USACO17JAN]Cow Dance Show S

 这道题目是二分舞台大小，为什么能用二分呢？因为如果mid成立 则mid~r都成立，如果mid不成立l~mid就都不成立，也就是严格单调，所以可以使用二分快速找到k。

check函数的思路：

实现：在舞台为k的情况下表演时间能否满足tmax。

思路：1.先给舞台上放k头牛按表演时间排序

　　　2.然后将余下的k+1~n在第一头牛的位置依次上舞台，每次上舞台后重新排序。

　　　3.最后第k头牛就是总耗时，判断是否满足tmax即可。

程序：

 1 #include
 2 using namespace std;
 3 int n,tmax,d[10010]={0};
 4 int check(int k)
 5 {
 6     int w[10010]={0};
 7     for(int i=1;i<=k;i++) w[i]=d[i];
 8     sort(w+1,w+1+k);
 9     for(int i=k+1;i<=n;i++)
10     {
11         w[1]+=d[i];
12         sort(w+1,w+1+k);
13     }
14     if(w[k]>tmax) return 0;
15     else return 1;
16 }
17 int main()
18 {
19     cin>>n>>tmax;
20     for(int i=1;i<=n;i++) cin>>d[i];
21     int l=1,r=n;
22     while(l+1!=r)
23     {
24         int mid=(l+r)/2;
25         if(check(mid))
26         {
27             r=mid;
28         }
29         else l=mid;
30     }
31     cout<endl;
32     return 0;
33 }