自动搬运

查看原文

来自洛谷，原作者为

	LOSpace ALL IN

搬运于2025-08-24 22:49:32，当前版本为作者最后更新于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;
}