| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 15192 | Accepted: 6855 |
Description
Input
Output
Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10
Sample Output
80
185
Hint
分析：又是这道题，不过发现这题还可以用堆来做，于是用堆来重新做一次。也用到了贪心的思想。先将所有商品按过期时间从小到大排序，然后建立一个商品价值的小根堆，依次遍历每个商品，如果发现当前堆的size小于过期日期，则说明现在卖出的商品个数小于其过期日期，就可以直接将该商品的价值丢进堆中;如果发现当前堆的size等于过期日期，则说明直到该商品的过期日期为止每一天都已经有商品卖出了，则比较当前商品价值与堆顶元素大小，如果大于，就将堆顶删除，再将该商品丢进堆中。最后堆中剩下的元素就是我们要卖出的元素，求和输出即可。
Code：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<iomanip> 6 #include<iostream> 7 #include<algorithm> 8 #define Fi(i,a,b) for(int i=a;i<=b;i++) 9 using namespace std; 10 const int N=1e4+7; 11 int n,heap[N],size,ans; 12 struct Node{int d,v;}a[N]; 13 bool cmp(Node x,Node y) 14 {return x.d<y.d;} 15 inline void insert(int x) 16 { 17 heap[++size]=x;int ka=size; 18 while(ka>1){ 19 if(heap[ka]<heap[ka/2]) 20 swap(heap[ka/2],heap[ka]),ka/=2; 21 else break;} 22 } 23 inline void delet() 24 { 25 heap[1]=heap[size--]; 26 int ka=1,s=2; 27 while(s<=size){ 28 if(s<size&&heap[s+1]<heap[s])s++; 29 if(heap[s]<heap[ka]){ 30 swap(heap[ka],heap[s]);ka=s;s=ka*2;} 31 else break;} 32 } 33 int main() 34 { 35 ios::sync_with_stdio(false); 36 while(cin>>n){Fi(i,1,n)cin>>a[i].v>>a[i].d; 37 sort(a+1,a+n+1,cmp);ans=0; 38 Fi(i,1,n)if(size<a[i].d)insert(a[i].v); 39 else if(size==a[i].d)if(a[i].v>heap[1])delet(),insert(a[i].v); 40 while(size>0){ans+=heap[1];delet();}cout<<ans<<"\n";} 41 return 0; 42 }
原文：https://www.cnblogs.com/cytus/p/9010607.html