【题目描述】#

在焦作太行路上，有一家烤鸡翅的生意火爆。因为好吃，所以卖的特别好。排队的人就特别多，经常有很多人买不到鸡翅。 鸡翅会在每分钟烤出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]范围内

题解#

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

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int x[250005], y[250005];
class comp
{
  public:
    bool operator()(long long a, long long b)
    {
        return y[a] < y[b];
    }
};
priority_queue<long long, vector<long long>, comp> Q;
int main()
{
    freopen("wing.in", "r", stdin);
    freopen("wing.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &x[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &y[i]);
    long long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += x[i];
        if (sum >= y[i])
            sum -= y[i], Q.push(i);
        else
        {
            if (!Q.empty())
            {
                if (y[Q.top()] > y[i])
                {
                    sum += y[Q.top()];
                    Q.pop();
                    sum -= y[i];
                    Q.push(i);
                }
            }
        }
    }
    printf("%d\n", Q.size());
}