[USACO17JAN]Cow Dance Show S更新ing

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

check函数的思路：

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

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

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

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

程序：

 1 #include<bits/stdc++.h>

 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<<r<<endl;

32     return 0;

33 }

还有一个写法就是用小根堆来写（点我科普大小根堆）

众所不周知小根堆可以自己排序所以省的时间就省在sort上了。

其他的只有一点值得注意：小根堆取首项用的是去。q.top();

程序：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,tmax,a[10010]={0};

 4 priority_queue<int,vector<int>,greater<int>> q;

 5 int check(int side)

 6 {

 7 //    int w[10010]={0};

 8     for(int i=1;i<=side;i++) q.push(a[i]);

 9     for(int i=side+1;i<=n;i++)

10     {

11         int op=q.top();

12         q.pop();

13         q.push(op+a[i]);

14 //        w[1]+=a[i];

15 //        sort(w+1,w+1+side);

16     }

17     int ans=0;

18     while(q.size())

19     {

20         ans=max(q.top(),ans);

21         q.pop();

22     }

23     if(ans>tmax) return 0;

24     else return 1;

25 }

26 int main()

27 {

28     scanf("%d%d",&n,&tmax);

29     for(int i=1;i<=n;i++) scanf("%d",&a[i]);

30     int l=1,r=n;

31     while(l+1!=r)

32     {

33         int mid=(l+r)/2;

34         if(check(mid)==1)

35         {

36             r=mid;

37         }

38         else l=mid;

39     }

40     printf("%d",r);

41     return 0;

42 }

巴特西

[USACO17JAN]Cow Dance Show S更新ing

最新文章

热门文章