保护花朵（选择性贪心）C++详解

问题 B: 保护花朵（密码：djlhql2023）
时间限制: 1 Sec 内存限制: 128 MB
提交: 168 解决: 193
Judge Mode:Std IO
File Name:
[提交][状态]
[题目描述]
约翰留下了 N 只奶牛呆在家里，自顾自地去干活了，这是非常失策的。他还在的时候，奶牛像往常一样悠闲地在牧场里吃草。可是当他回来的时候，他看到了一幕惨剧：他的奶牛跑进了他的花园，正在啃食他精心培育的花朵！约翰要立即采取行动，挨个把它们全部关回牛棚。 约翰牵走第 i 头奶牛需要 T i 分钟，因为要算来回时间，所以他实际需要 2 · T i 分钟。第 i 头奶牛如果还在花园里逍遥，每分钟会啃食 D i 朵鲜花。但只要约翰抓住了它，开始牵走它的那刻开始，就没法吃花了。请帮助约翰写一个程序来决定押送奶牛的顺序，使得花朵损失的数量最小。
输入
第一行：单个整数 N，1 ≤ N ≤ 100000
第二行到第 N + 1 行：第 i + 1 行有两个整数 T i 和 D i ，2 ≤ T i ≤ 10^6 ,1 ≤ D i ≤ 100
输出
单个整数：表示约翰损失的最小花朵数量
样例输入
6
3 1
2 5
2 3
3 2
4 1
1 6
样例输出
86
提示
解释 依次制服第六头，第二头，第三头，第四头，第一头和第五头

##错解
首先看到样例，我就想到了，这不就是个贪心吗，也没多想就把d从大到小排序，依次累加答案，于是光荣地获得了18分的好成绩。
排序代码：

bool cmp(node x, node y) {
	return x.d > y.d;
}
1
2
3

错解完整代码：

#include 
using namespace std;
#define int long long
const int N = 100010;
int n;
struct node {
	int t, d;
} a[N];
bool cmp(node a, node b) {
	return a.d > b.d;
}
int ans = 0;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t >> a[i].d;
		sum += a[i].d;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		ans += (2 * a[i].t * (sum - a[i].d));
		sum -= a[i].d;
	}
	cout << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

正解

考虑两个cow，x，y我们的初衷是尽可能的少破坏花，那就意味着要先制服破坏力大的且时间短的。
对于x，y：x的破坏力=$2\ast tx\ast (sum-dx)$=$2\ast tx\ast dy$(因为此时只有两个奶牛)
y的破坏力=$2\ast ty\ast (sum-dy)$=$2\ast ty\ast dx$
所以排序式是：

bool cmp(node a, node b) {
	return 2 * a.d * b.t > 2 * b.d * a.t;
}
1
2
3

完整AC代码如下：

#include 
using namespace std;
#define int long long
const int N = 100010;
int n;
struct node {
	int t, d;
} a[N];
bool cmp(node a, node b) {
	return 2 * a.d * b.t > 2 * b.d * a.t;
}
int ans = 0;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].t >> a[i].d;
		sum += a[i].d;
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		ans += (2 * a[i].t * (sum - a[i].d));
		sum -= a[i].d;
	}
	cout << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30