UOJ Logo insilent的博客

博客

#63. 超市

2018-02-24 03:06:20 By insilent

解题思路:

用贪心的思想,将商品的价值从大到小排序,找到销售的最大期限,用ti数组标记,如果它的期限没有被占用,就在该天销售,如果占用,则从它的前一天开始向前查找有没有空闲的日期,如果有则占用。这样就可以得到最大销售量。


以下是我的贪心写法:


#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
struct subject{
    int price,deadline;
};
bool cmp(subject a,subject b)
{
    return a.price>b.price;
}
subject op[100005];
bool ti[100005];
int ans;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&op[i].price,&op[i].deadline);
    }
    sort(op+1,op+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(!ti[op[i].deadline])
        {
            ans+=op[i].price;
            ti[op[i].deadline]=1;
        }
        else
        {
            for(int j=op[i].deadline-1;j>=1;j--)
            {
                if(!ti[j])
                {
                    ans+=op[i].price;
                    ti[j]=1;
                    break;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}



但据说本题应是贪心+并查集 以下引用于 kuangbin

这里其实用贪心做,并查集只是用来作为工具,使得速度更加快。 题目大意是买卖N件东西,每件东西都有个截止时间,在截止时间之前买都可以,而每个单位时间只能买一件。问最大获利。 如果购买不冲突,那么全部买下来就可以了。存在冲突,就需要取舍。显然在冲突的时候我们选择价格高的更优,如此就可以用贪心的算法。先将物品按照价格从高到底的顺序排列,购买一个就在时间点上做一个标记,只要不冲突就可以购买。 如何快速找到第一个不冲突的时间点呢,个人感觉使用并查集很好得解决了这个问题。 这里并查集的作用类似于链表指针,压缩的过程就是删掉节点的过程。从而在O(1)的时间内找到那个不冲突的点。


/*
POJ 1456
贪心处理。
按照获利p从大到小排序。
处理的时候选择最后的一个不冲突点。

用并查集实现链表的作用,快速找到不冲突点
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#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)//按p从大到小排序。d没有关系
{
    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);
    }
    return 0;
}

评论

poorpool
实际上还有一种做法是先按时间排序然后维护权值为价值的小根堆

发表评论

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