P3611 【[USACO17JAN]Cow Dance Show奶牛舞蹈】

想了一下还是不发以前做过的水题了，意义也不是很大，现在的话大概只有洛谷黄题以上才会收录了哦~~~

喵了个咪的题面~~

洛谷题解dalao不是P党就是优先队列，看的我作为一个新手蒟蒻好慌啊。。。

这题用二分加冒泡（你没有看错，用sort反而会超时）

先用二分决定k的值，然后判断这个k可不可行，然后继续二分，重复刚才操作

具体解释看代码：

 #include<cmath>

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,tmax,t,l,r;

 int a[],b[];//变量就不过多介绍了，大家自己看

 int shu(int k){//函数，判断当前k是否可行

     for(int i=;i<=k;i++){

             b[i]=a[i];

 }//前k个奶牛 sort(b+1,b+1+k);//排序，因为当前数组是无序的，所以用sort

     for(int i=k+;i<=n;i++){

         if(b[k]>tmax)return tmax+;//如果当前已经超过了，就直接退出循环

         b[]+=a[i];//定向思维是减去最小的时间，但未必必须这样做

         for(int j=;j<=k;j++){//传说中的冒泡粉墨登场~~~此处用sort真的会超时，不信你们自己去试试

             if(b[j]>=b[j-]){//如果已经在合适的位置，就退出循环

                 break;

             }

             int x=b[j];//否则交换

             b[j]=b[j-];

             b[j-]=x;

         }

     }

     return b[k];//返回最大的时间

 }

 int main(){

     freopen("cowdance.in","r",stdin);

     freopen("cowdance.out","w",stdout);//这两句话当废话处理，是我在USACO主网站上交的时候加上去的

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

     for(int i=;i<=n;i++){

         scanf("%d",a+i);

 }//读入 l=1,r=n;//二分的准备活动（- 一二三四，二二三四）

 while(l<r){//二分开始，在left小于（等于）right的时候执行

         int mid=(l+r)/;//取中间值

         if(shu(mid)>tmax)l=mid+;//如果当前k不满足要求，增大k的值

         else r=mid-;//反之缩小

     }

     printf("%d\n",l);//输出

     return ;

 }

嘿嘿~~~ 如果你们Ctrl C+Ctrl V的话，会发现一个很神奇的现象：我的程序不能AC！！！

仔细看看注释，我相信你可以改出来的哦~~~

嘻嘻新人开博鼓励一下啦！！！

P3611 【[USACO17JAN]Cow Dance Show奶牛舞蹈】的相关教程结束。