luogu3545(POI)

发表于 | 分类于

POI中的水题，我们尽可能多的去满足顾客，直到当前顾客不能被满足，我们就找到之前需求最大的的顾客，然后判断一下与当前顾客谁的需求更大一些，若当前顾客需求大则跳过他，否则踢掉之前需求最大的顾客，来满足当前顾客。这样答案不会变得更差，而且我们还有了更多的货物更有可能满足后来的人。“找到之前需求最大的顾客”我们可以用堆来实现。整个过程时间复杂度为O(nlogn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
long long a[250004],b[250005];
long long n;
long long rest;
long long k;
struct dou
{
    long long num,val;
};
bool operator > (dou x,dou y)
{
    return x.val>y.val;
}
bool operator < (dou x,dou y)
{
    return x.val<y.val;
}
priority_queue<dou> q;
long long ans;
bool vis[250005];
int main()
{
    scanf("%d",&n);
    for(long long i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(long long i=1;i<=n;i++)
        scanf("%d",&b[i]);
    dou t;
    for(long long i=1;i<=n;i++)
    {
        rest+=a[i];
        if(rest>=b[i])
        {
            ans++;
            rest-=b[i];
            t.val=b[i];
            t.num=i;
            vis[i]=1;
            q.push(t);
        } 
        else
        {
            if(q.empty())continue;
            t=q.top();
            if(b[i]>=t.val)continue;
            q.pop();
            rest+=t.val;
            rest-=b[i];
            vis[t.num]=0;
            vis[i]=1;
            t.num=i;
            t.val=b[i];
            q.push(t);
        }
    }
    printf("%d\n",ans);
    for(long long i=1;i<=n;i++)
        if(vis[i]) printf("%d ",i);
    return 0;
}