题解 P3093 【[USACO13DEC]牛奶调度Milk Scheduling】

肛道理这题是不是和今年noid2t2的80分暴力有点异曲同工之处啊。。 异曲同工个p啊这完全就是一样的做法好么 不会用stl的蒟蒻手写了个堆冷静了下 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int n,f[1000000],ans,k,d; struct lsg{int x,y;}a[1000000]; void putit(int x){//在堆中插入 f[++d]=x;int kk=d;while (kk!=1&&f[kk/2]<f[kk]) swap(f[kk],f[kk/2]),kk/=2; }void outit(){//在堆顶删除 f[1]=f[d--];int x=0,y=1;while (x!=y){ x=y;if (x*2<=d&&f[x*2]>f[y])y=x*2; if (x*2+1<=d&&f[x*2+1]>f[y])y=x*2+1;swap(f[y],f[x]); } }bool pd(lsg x,lsg y){return x.x>y.x;} signed main(){ ios::sync_with_stdio(false); cin>>n;for (int i=1;i<=n;i++)cin>>a[i].y>>a[i].x; sort(a+1,a+1+n,pd);k=1;for (int i=10000;i>=1;i--){//将时间逆序枚举 while (a[k].x==i&&k<=n)putit(a[k].y),k++; if (d)ans+=f[1],outit();//就那样吧，能取就贪心取最大的 } cout<<ans<<endl; } ```