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

2017-10-08 21:11:00


肛道理这题是不是和今年noid2t2的80分暴力有点异曲同工之处啊。。

异曲同工个p啊这完全就是一样的做法好么

不会用stl的蒟蒻手写了个堆冷静了下

#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;
}