2020年蓝桥杯国赛-答疑

题目

题目链接

题解

贪心。

有点像“排队打水”。

比较好想，而且我甚至都能证明。

贪心思路：按照 s + a + e s+a+e s+a+e 从小到大排序即可。

证明：

首先，每个人的 s s s 和 a a a 都可以看成是一个部分，记为 d d d，因为这段时间只是干的事不同，本质都是打卡前花费的时间。

规定 p i p_i pi​ 表示第 i i i个人， a i a_i ai​ 和 b i b_i bi​ 分别对应第 i i i个人的 d d d 和 e e e。

排好序后为 P 1 P 2 . . . P i P i + 1 . . . P n P_1P_2...P_iP_{i+1}...P_n P1​P2​...Pi​Pi+1​...Pn​，为了方便令 j = i + 1 j=i+1 j=i+1。

显然无论是否交换 P i P_i Pi​ 与 P j P_j Pj​ 的顺序都不会影响二者以外的人的打卡时间，所以变化的就只有二者的打卡时间，从而影响最终结果。

假设除 i 、 j i、j i、j外的人的打卡时间之和记为 S S S，答案应为 S + S+ S+ P i P_i Pi​ 打卡时间 + P j +P_j +Pj​ 打卡时间。

记 a 1 + b 1 + a 2 + b 2 + . . . + a i − 1 + b i − 1 a_1+b_1+a_2+b_2+...+a_{i-1}+b_{i-1} a1​+b1​+a2​+b2​+...+ai−1​+bi−1​ 为 S i − 1 S_{i-1} Si−1​，交换顺序前， P i P_i Pi​ 打卡的时间为 S i − 1 + a i S_{i-1}+a_i Si−1​+ai​， P j P_j Pj​ 的打卡时间为 S i − 1 + a i + b i + a j S_{i-1}+a_i+b_i+a_j Si−1​+ai​+bi​+aj​，对应答案为 S + ( S i − 1 + a i ) + ( S i − 1 + a i + b i + a j ) S+(S_{i-1}+a_i)+(S_{i-1}+a_i+b_i+a_j) S+(Si−1​+ai​)+(Si−1​+ai​+bi​+aj​)；交换顺序后，即序列为 P 1 P 2 . . . P j P i . . . P n P_1P_2...P_jP_{i}...P_n P1​P2​...Pj​Pi​...Pn​，那么 P i P_i Pi​ 打卡的时间为 S i − 1 + a j + b j + a i S_{i-1}+a_j+b_j+a_i Si−1​+aj​+bj​+ai​， P j P_j Pj​ 的打卡时间为 S i − 1 + a j S_{i-1}+a_j Si−1​+aj​，对应答案为 S + ( S i − 1 + a j + b j + a i ) + ( S i − 1 + a j ) S+(S_{i-1}+a_j+b_j+a_i)+(S_{i-1}+a_j) S+(Si−1​+aj​+bj​+ai​)+(Si−1​+aj​)。

将 a i + b i a_i+b_i ai​+bi​ 记为 s u m i sum_i sumi​， a j + b j a_j+b_j aj​+bj​ 记为 s u m j sum_j sumj​，则交换前答案为 S + 2 S i + s u m i + a i + a j S+2S_i+sum_i+a_i+a_j S+2Si​+sumi​+ai​+aj​，交换后答案为 S + 2 S i + s u m j + a i + a j S+2S_i+sum_j+a_i+a_j S+2Si​+sumj​+ai​+aj​。可见，影响最终答案的是 s u m i sum_i sumi​ 与 s u m j sum_j sumj​ 的大小关系。

最终可以判断 s u m sum sum 小的在前更佳，即 a + b a+b a+b 小的，又即 s + a + e s+a+e s+a+e 小的。

（总而言之，就是交换法证明贪心，最简单的证明了）

代码

#include
using namespace std;
typedef long long LL;
LL ans = 0, sum = 0;
int n;

const int N = 1100;

struct node {
	int a, b, c, d;
} s[N];

bool cmp (node a, node b) {
	return a.d > n;
	for (int i = 0;i > s[i].a >> s[i].b >> s[i].c, 
		s[i].d = s[i].a + s[i].b + s[i].c;
	
	sort (s, s + n, cmp);
	
	for (int i = 0;i