P9556 题解

LOSpace · 2023-08-19 12:19:37 · 题解

原题链接

解题思路

可以使用一个结构体数组存下一笔订单的交付时间和交付数量。因为要在规定时间内完成对应的任务，所以可以进行排序：以交付时间为第一关键字从小到大，再以交付数量为第二关键字从小到大排序。当前任务即为未完成的最靠前订单。

要判断能不能完成一批订单，就要判断到了某一笔订单的交付时间存货够不够交付这一笔订单。如果不够就说明不能完成这一批订单；反之存货减少这一笔订单所需货物数量，然后继续。

注意：要开 long long 。

代码实现

#include<bits/stdc++.h>
using namespace std;
int T;
struct node {
    long long a, b;
};
bool cmp(node x, node y) {
    return x.a == y.a ? x.b < y.b : x.a < y.a;
}
int main() {
    for (scanf("%d", &T); T --; ) {
        long long n, k, now, last;
        bool flag;
        now = last = flag = 0;
        scanf("%lld%lld", &n, &k);
        node q[n + 5];
        for (int i = 0; i < n; i ++)
            scanf("%lld%lld", &q[i].a, &q[i].b);
        sort(q, q + n, cmp);
        for (int i = 0; i < n && !flag; i ++) {
            now += (q[i].a - last) * k;
        //当前存货为之前存货加上这次交付时间
         //减去上一次交付时间乘上每天生产数量
            if (now < q[i].b) flag = true;
            else {
                last = q[i].a;
                now -= q[i].b;
            }
        }
        if (!flag) puts("Yes");
        else puts("No");
    }
    return 0;
}