UOJ Logo qiao的博客

博客

#63 超市

2019-02-14 11:08:35 By qiao

需考虑: (1) 在固定的时间内是否可以将所有物品买完; (2) 按物品的价值大小排序;

定义find函数,如果物品所在可售的最大事件未被占用,标记并将物品可售时间缩短1.

在可用时间结束后,ans为最大。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=10010;
int f[Maxn];
struct Node{
    int p,d;
}node[Maxn];
bool cmp(Node a,Node b){
    return a.p>b.p;
}
int find(int x){
    if(f[x]==-1)  return x;
    return f[x]=find(f[x]);
}
int main(){
    int n;
    while(scanf("%d",&n)==1){
        memset(f,-1,sizeof(f));        
        for(int i=0;i<n;i++)
            scanf("%d%d",&node[i].p,&node[i].d);
        sort(node,node+n,cmp);        
        int ans=0;
        for(int i=0;i<n;i++){
            int t=find(node[i].d);        
            if(t>0){
                ans+=node[i].p;
                f[t]=t-1;
            }
        }
        printf("%d\n",ans);
    }
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。