[USACO05NOV] Cows Doing Acrobatics
Background to the topic
Farmer John raised it.\(N\) The cows, they've pressed\(1\sim N\) Unbeknownst to FJ, all of his cows dream of escaping from the farm to join the circus. But the cows soon discover that their clumsy hooves can't hold their ground on a wire or a wobbly swing (they also try to launch themselves out of a cannon, with predictably disastrous results). In the end, they decided to practice the simplest of acrobatics: stacking all the cows on top of each other, so that, for example, the first one stood on top of the second one, and the second one stood on top of the third one... The bottom one is number one.\(N\) A cow.
Title Description
Each cow has its own weight as well as strength, numbered\(i\) The weight of the cows in the\(W_i\)The force is\(S_i\)。
When a cow is standing on top of other cows she is crushed to a certain extent, and we may call the extent to which she is crushed her crushing index. For any cow, her squash index is equal to the total weight of all the cows on top of her (excluding herself, of course) minus her strength. When the cows are stacked in a certain order, their total squash index is the squash index of the cow that is squashed the most.
Your task is to help the cows figure out a stacking sequence that minimizes the total squash index.
input format
First line an integer\(N\)。
accept\(N\) Lines, two integers per line\(W_i\) cap (a poem)\(S_i\)。
output format
One integer in a row indicates the minimum total squash index.
Sample #1
Sample Input #1
3
10 3
2 5
3 3
Sample Output #1
2
draw attention to sth.
insofar as\(100\%\) of the data.\(1 \le N \le 5\times 10^4\)，\(1 \le W_i \le 10^4\)，\(1 \le S_i \le 10^9\)。
Title Link:/problem/P1842
Thoughts:
In this question we just got the question, we can start with a simulation, we can define a structure that stores two properties of cows, strength and weight. At first there is not too good idea to calculate the minimum squash index, but we can intuitively guess that we want to make the group of cows when the
In that the cow that is squashed the most has the smallest squash index possible, so aren't we trying to make the sum of the weights of all the cows above the squashed one as small as possible and to make that cow as strong as possible, right? So it's not just the body weight that makes our lowest squash index relevant
related and also related to the strength of the cow, so that while adopting a sorting strategy, we can't just sort according to the weight or according to the strength of this one element, we must combine the two attributes, we might as well conjecture that according to theSome combination of weight and strength.toward
Sorting, which can beThe Difference Between Weight and Strengthto sort, or it could beSum of strength and weightto sort, and as soon as we show that the total squash index we get with some sort of sorting rule is the smallest, then we've successfully demonstrated the feasibility of our scheme, right?
Proof of a greedy strategy:
- We might first conjecture that we sort by the sum of strength and weight, with the smaller sum of strength and weight at the front, and vice versa at the back. Then we need to show that under this ordering rule, the total squash index we get is the smallest total squash index
Let's assume that the ith cow its squash index is the total squash index, then the total weight of all the cows in front of it is\(w_1\)+\(w_2\)+.... .w(i-1), at which point the total squash index isw1+w2+....+w(i-1)-siSo how do we go about proving that this squash index is the minimum?
We can try to swap any two rows of cows, e.g., we let the ith cow be swapped with the i-1th cow, then the total squash index at this point becomesw1+w2+...wi-s(i-1)We just need to prove thatw1+w2+..w(i-1)-si<w1+w2+...+wi-s(i-1)can immediately (do sth)
Since we are sorting in ascending order by the sum of weight and strength, then we must havew(i-1)+s(i-1)<wi+siThis equation,Observing the above inequality, there are only four places where wi,w(i-1),si,s(i-1) are not the same, we havew(i-1)+s(i-1)<wi+siThis equation
After shifting the terms on both sides you getw(i-1)-si<wi-s(i-1), which happens to be obtained by morphing the above equation, then we have successfully proved the feasibility of our strategy
- Other cases, such as sorting in ascending order by the difference between weight and strength, are also guessable in this way, and we can also prove the feasibility of this strategy on our own as well, and if we can show that the approach of our current strategy is the optimal solution, we can adopt it, but the question
In this case, it is not desirable, and we can prove it for ourselves.
Code:
#include<algorithm>
#include<iostream>;
using namespace std.
const int N = 5e4 + 10; //Store the weight and strength attributes in a structure.
// Use a structure to store the weight and strength attributes.
struct node {
int w; int s; struct node {
struct node { int w; int s; int
struct node { int w; int s; }a[N].
int n; struct node { int w; int s; }a[N]; int n
// Sort the nodes in ascending order by the sum of their strength and weight.
bool compare(node A, node b) {
return + < + ;
}
int main()
cin >> n; } int main() {
cin >> n; for (int i = 1; i <= n; i++) {
for (int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].s.
}
sort(a + 1, a + 1 + n, compare);
// The answer is most casually initialized to a minimum value first
int res = -2e9; int t = 0; //s
int t = 0; for (int i = 1; i
for (int i = 1; i <= n; i++) {
// The result takes the maximum value of the squash index
res = max(res, t - a[i].s);
t += a[i].w;
}
cout << res.
res; return 0; }
}
Summary:
A lot of times the greedy strategy is based on our intuition to get the idea, but we sometimes can't give a rigorous proof process like in this question, but we when we can't come up with any counterexamples, we can try our greedy strategy!
All in all, the greedy strategy is many times what our common sense tells us we should do, and as long as we can't come up with any counterexamples, we can try the greedy strategy, and sometimes we can go ahead and try the rigorous math to prove that our strategy is correct!