COGS 2235 烤鸡翅 - NekoMio's Blog

【题目描述】#

在焦作太行路上，有一家烤鸡翅的生意火爆。因为好吃，所以卖的特别好。排队的人就特别多，经常有很多人买不到鸡翅。鸡翅会在每分钟烤出Xi个，每分钟也只会卖给一个客人，第i个客人需要买Yi个。因为生意火爆，老板可以选择在这分钟不卖给这个客人鸡翅，或者卖给这个顾客他需要的鸡翅，如果现在剩余的鸡翅不够，那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅，他必须离开队伍。现在给定N分钟，且已经知道每分钟烤出的鸡翅个数Xi，也知道每个客人需要鸡翅的Yi个数，现在老板想知道，如何合理安排卖给与拒绝，最多可以满足多少人

【输入格式】#

第一行一个正整数N，表示有N分钟的时间卖鸡翅第二行N个用空格隔开的整数 X1，X2……Xn，Xi表示第i分钟会有Xi个鸡翅烤出第三行N个用空格隔开的整数Y1，Y2……Yn，Yi表示第i分钟的顾客需要Yi个鸡翅

【输出格式】#

一个整数，表示最多可以满足买到鸡翅的人数。

【样例输入】#

6
2 2 1 2 1 0
1 2 2 3 4 4

【样例输出】#

3

【数据范围】#

50% 数据保证 N<=1000 100% 1<=N<=250000 Xi,Yi都在[0,10^9]范围内

题解#

能卖就卖
卖不了了如何以前有人买的数目比他多
那就不卖给以前的那个人了也就是收回来
可后悔的贪心，长见识了。主要使用优先队列

1
#include <cstdio>
2
#include <cstring>
3
#include <queue>
4
using namespace std;
5
int x[250005], y[250005];
6
class comp
7
{
8
  public:
9
    bool operator()(long long a, long long b)
10
    {
11
        return y[a] < y[b];
12
    }
13
};
14
priority_queue<long long, vector<long long>, comp> Q;
15
int main()
16
{
17
    freopen("wing.in", "r", stdin);
18
    freopen("wing.out", "w", stdout);
19
    int n;
20
    scanf("%d", &n);
21
    for (int i = 1; i <= n; i++)
22
        scanf("%d", &x[i]);
23
    for (int i = 1; i <= n; i++)
24
        scanf("%d", &y[i]);
25
    long long sum = 0;
26
    for (int i = 1; i <= n; i++)
27
    {
28
        sum += x[i];
29
        if (sum >= y[i])
30
            sum -= y[i], Q.push(i);
31
        else
32
        {
33
            if (!Q.empty())
34
            {
35
                if (y[Q.top()] > y[i])
36
                {
37
                    sum += y[Q.top()];
38
                    Q.pop();
39
                    sum -= y[i];
40
                    Q.push(i);
41
                }
42
            }
43
        }
44
    }
45
    printf("%d\n", Q.size());
46
}