题号 NC25043
名称 Protecting the Flower
来源 USACO英文版-2007 January Contest-Silver

解题思路

题目要求奶牛总共破坏的花朵最少，牵奶牛的顺序至关重要。

假设有两头奶牛 cow1 和 cow2，如果先牵走第 1 头奶牛，那么破坏的花朵是 2 * cow1[0] * cow2[1]，如果先牵第 2 头奶牛，共破坏花朵 2 * cow2[0] * cow1[1]。
根据题意， 先牵破坏花朵少的对应的那头奶牛。

确定了牵奶牛的顺序，再计算花朵的总破坏量。
使用 sum 记录所有奶牛每分钟花朵破坏量，每牵走一头奶牛，减去其对应的破坏量。将 sum * cows[i][0] * 2 累计加入结果 ans。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool comp(vector<int> &cow1, vector<int> &cow2){
    return cow1[0]*cow2[1] < cow2[0]*cow1[1];
}
int main(){
    int N;
    cin >> N;
    vector<vector<int>> cows(N, vector<int>(2));
    for(int i=0; i<N; ++i){
        cin >> cows[i][0] >> cows[i][1];
    }
    sort(cows.begin(), cows.end(), comp);
    long long sum = 0;
    for(int i=0; i<N; ++i){
        sum += cows[i][1];
    }

    long long ans = 0;
    for(int i=0; i<N-1; ++i){
        sum -= cows[i][1];
        ans += sum * cows[i][0] * 2;
    }
    cout << ans << endl;
    return 0;
}