贪心：保卫花园

题目P2878 [USACO07JAN] Protecting the Flowers S - 洛谷题目概述每头牛都呆在数组的某个坐标上并且每分钟会吃掉i朵花问如何排序把牛牵回坐标0处使花的损失最小。求最小吃掉花的数量。思路每一波吃掉花的数量 其他奶牛的总吃草量 * 这头选中的奶牛走到坐标0的时间。因此最终结果其实就是确定“牵牛”的顺序。因此就是对所有的奶牛排序最重要的就是找出排序规则。推导规律重要在确定好 (假设确定好) 顺序的序列中拿出相邻的两个元素如果交换这两个元素对前面以及后面确定好顺序的序列的结果不造成影响此时就可以根据这两个元素交换前后的结果推导出排序的规则执行1拿出相邻的 奶牛j和一头奶牛i执行2如果这两头奶牛交换牵走的顺序对 j 前面所有奶牛的总吃草量有没有影响对 i 后面所有奶牛的总吃草量有没有影响 没有影响。i 和 j 交换顺序都不影响前面先吃一直吃到 i 和 j ...... 对前面没有影响。虽然i和j交换顺序但i 和 j 吃草的总时间没有变所以对后面也没有影响。执行3推导排序规则把它们同时除以 dj di可以变形为tᵢ / dᵢ tⱼ / dⱼ这个不等式的含义是​​任务i的“单位损失” (tᵢ / dᵢ) 小于任务j的“单位损失” (tⱼ / dⱼ)​​。单位损失越大紧急度越高。总代码#include iostream #include algorithm using namespace std; typedef long long LL; const int N 1e5 10; int n; LL sum 0, ret 0; struct node { int t; int d; }a[N]; bool cmp(node x, node y) { return x.t * y.d y.t * x.d; //除法会导致浮点数丢失这里应该写成乘法 } int main() { cin n; for (int i 1; i n; i) { cin a[i].t a[i].d; sum a[i].d; //记录所有的吃草量 } sort(a1, a1n, cmp); for (int i 1; i n; i) { sum - a[i].d; //减去每回合的补救 ret a[i].t*2*sum; } cout ret endl; return 0; }时间复杂度为O(n log n) 。