奶牛运送最小总损失问题 - 核心思路

一、核心算法：贪心算法（局部最优推导全局最优）

贪心算法的核心是找到局部最优判断规则，通过每一步的局部最优选择，最终得到全局最优解，本问题的核心就是推导奶牛运送的最优排序规则。

二、关键：两两奶牛对比推导排序规则

1. 假设仅有两头奶牛 A(t1, d1) 和 B(t2, d2)，分析两种运送顺序的损失：
   • 先送A再送B：额外损失为 2 * t1 * d2（运送A的往返时间内，B持续毁花）；
   • 先送B再送A：额外损失为 2 * t2 * d1（运送B的往返时间内，A持续毁花）。
2. 最优顺序选择：取损失更小的方案，即比较上述两个损失值：
   • 若 2 * t1 * d2 < 2 * t2 * d1，简化为 t1 * d2 < t2 * d1，优先送A；
   • 若 2 * t2 * d1 < 2 * t1 * d2，简化为 t2 * d1 < t1 * d2，优先送B。
3. 全局排序规则：对于任意两头奶牛，当 A.t * B.d < B.t * A.d 时，A排在B之前运送，该局部最优规则可推导出全局最小总损失。

三、整体执行核心流程

1. 输入所有奶牛的 t（单程运送耗时）和 d（每分钟毁花数）数据；
2. 按照上述推导的贪心排序规则，对所有奶牛进行排序；
3. 遍历排序后的奶牛，先累计当前奶牛的等待损失，再更新总运送耗时：
   • 损失累计：当前总耗时 × 该奶牛的 d（该奶牛等待前面奶牛运送的时间内，造成的毁花损失）；
   • 耗时更新：总耗时 += 该奶牛的往返耗时（2 * t），供后续奶牛计算损失使用；
4. 最终累计的损失即为最小总损失。

四、核心细节保障

1. 数据类型：需使用大范围整数类型（如 long long），避免总耗时和总损失超出数据范围导致溢出；
2. 排序严谨性：使用乘法比较（t1*d2 < t2*d1）而非除法，避免整数除法带来的精度丢失，保证排序结果正确；
3. 执行顺序：必须「先算损失，再更耗时」，因为当前奶牛的损失是基于前面奶牛的总运送时间，而非包含自身运送时间。

#define int long long
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define sep "================"
#define ios                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
const int inf = 2e18 + 9;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
typedef pair<int, int> pll;
typedef long double db;
inline void pt(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        pt(x / 10);
    putchar(x % 10 + '0');
}
inline void print(int x) { pt(x), puts(""); }
inline void print(pll x) { pt(x.fi), putchar(' '), pt(x.se), putchar('\n'); }
inline void print(vi &vec)
{
    for (const auto t : vec)
        pt(t), putchar(' ');
    puts("");
}
inline void print(vector<pll> &vec)
{
    puts(sep);
    for (const auto v : vec)
    {
        print(v);
    }
    puts(sep);
}
inline int comb(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
    k = min(k, n - k);
    int numerator = 1;
    int denominator = 1;
    for (int i = 1; i <= k; ++i)
    {
        numerator *= (n - k + i);
        denominator *= i;
        int g = __gcd(numerator, denominator);
        numerator /= g;
        denominator /= g;
    }
    return numerator / denominator;
}
void init()
{
}
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
inline int read()
{
    int x = 0;
    short f = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-')
        c = getchar();
    if (c == '-')
        f = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    x *= f;
    return x;
}
inline int qsm(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
        {
            res *= a;
        }
        b >>= 1;
        a *= a;
    }
    return res;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dirx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int diry[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct cow
{
    int t , d ; 
};
bool cmp(const cow & a , const cow & b)
{
    return a.t * b.d < b.t * a.d ;
}
void work()
{
    int n ; cin >> n ;
    vector<cow>a(n) ; 
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i].t >> a[i].d ;
    }
    sort(all(a) , cmp) ; 
    int time = 0 ;
    int ans = 0 ; 
    for(int i = 0 ; i < n ; i++)
    {
        ans = ans + time * a[i].d ;
        time += 2 * a[i].t ;
    }
    cout << ans << endl  ;
}
signed main()
{
    init();
    ios;
    int t = 1;
    while (t--)
    {
        work();
    }
    return 0;
}