Day 13 · 贪心入门：局部最优通向全局最优

题意：n 个人排队接水，第 i 个人要接 Tᵢ 分钟。一个人的等待时间不算自己接水的时间。 要你排出一种顺序，让所有人的平均等待时间最小，并输出这个顺序和平均等待时间（保留两位小数）。 如果两个人的接水时间相同，编号更小的排前面。

思路

贪心策略：接水时间短的先上。

为什么？一个人接水的时候，他后面所有人都在等他。所以一个人接水时间越长， 他被「算进别人的等待时间」里的次数就越多。

换句话说是这样：排在第 i 位的人（从 1 数），他的接水时间会被后面 n − i 个人各等一次。 所以他对总等待时间的贡献是 Tᵢ × (n − i)。

乘数 (n − i) 在队伍前面很大、后面很小。要让总和最小， 就应该让大的 Tᵢ 配上小的乘数 —— 也就是让接水慢的人排到后面去。

10
56 12 1 99 1000 234 33 55 99 812

3 2 7 8 1 4 9 6 10 5
291.90

第一行输出的是人的编号（不是时间）。按时间升序排：1 (3号) → 12 (2号) → 33 (7号) → 55 (8号) → 56 (1号) → 99 (4号) → 99 (9号) → 234 (6号) → 812 (10号) → 1000 (5号)。
注意两个 99：4 号在 9 号前面，因为 4 号编号更小 —— 这就是「时间相同按编号」的体现。

完整代码

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

struct Person {
    int id;   // 原来的编号（1 开始）
    int t;    // 接水时间
};

Person a[1005];

// 排序规则：接水时间小的排前面；时间相同时编号小的排前面
bool cmp(const Person &p, const Person &q){
    if(p.t != q.t) return p.t < q.t;
    return p.id < q.id;                 // ★ 时间相同按编号升序，不能漏
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        cin >> a[i].t;
    }
    sort(a + 1, a + n + 1, cmp);        // 下标从 1 开始，所以是 a+1 到 a+n+1

    long long total = 0;                // ★ 总等待时间最大约 5×10^11，必须 long long
    for(int i = 1; i <= n; i++){
        // 排在第 i 位的人接水时，后面 n-i 个人都在等他
        total += 1LL * a[i].t * (n - i); // ★ 1LL 先转 long long，再乘，防止中途溢出
    }

    for(int i = 1; i <= n; i++){
        if(i > 1) cout << " ";
        cout << a[i].id;
    }
    cout << "\n";
    // ★ 先转 double 再除，否则会做整数除法，小数部分直接没了
    cout << fixed << setprecision(2) << (double)total / n << "\n";
    return 0;
}

易错点

• 不用 long long：总等待时间能到 5×10¹¹，int 存不下，会输出负数或者莫名其妙的数。
• 乘法写成 a[i].t * (n - i)：两边都是 int，会先按 int 算完再赋给 long long，中间就已经溢出了。
  必须写 1LL * a[i].t * (n - i)，让编译器一开始就按 64 位算。
• 平均值写成 total / n：这是整数除法，2919 / 10 会得到 291 而不是 291.9。
  要写 (double)total / n，并且加上 fixed << setprecision(2) 才会输出两位小数。
• 输出的是编号不是时间：第一行要输出 3 2 7 8 …（人的编号），把接水时间输出出去就废了。
• 时间相同时忘了按编号升序：样例里两个 99 就是专门用来考这个的，顺序错了会 WA。
• 数组下标从 1 开始却只开了 1000：题目 n 最大 1000，需要用到 a[1000]，所以至少开 1001，本文开 1005 留余量。

题意：有一堆纪念品，每件有个价格。要把它们分组发下去，规则是： 每组最多 2 件，而且每组两件的价格之和不能超过 w。问最少要分多少组。

思路

贪心策略：先排序，然后每次拿「现在最重的」去试试能不能和「现在最轻的」凑一组。

能凑上就两个一起走；凑不上就说明最重的那件跟谁配都超标，只能自己占一组。

为什么这样贪是对的

用交换论证，重点想清楚一件事：最重的那件纪念品怎么办最划算？

设现在最重的是 r，最轻的是 l。假设 P_l + P_r ≤ w（它俩能配）。

100
9
90
20
20
30
50
60
70
80
90

6

排序后：20 20 30 50 60 70 80 90 90。配对过程：
90 配 20 → 110 超标，90 单独一组；
90 配 20 → 同样超标，90 单独一组；
80 配 20 → 100 ✅ 一组；70 配 20 → 90 ✅ 一组；60 配 30 → 90 ✅ 一组；50 剩自己 → 一组。
一共 6 组。

完整代码

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

int p[30005];

int main(){
    int w, n;
    cin >> w;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> p[i];

    sort(p, p + n);              // 从小到大排序，双指针才好用

    int l = 0, r = n - 1, ans = 0;
    while(l <= r){               // ★ 用 <= 而不是 < ，否则中间剩一个会被漏掉
        if(l == r){
            ans++;               // ★ 只剩一件，自己一组
            break;
        }
        if(p[l] + p[r] <= w){
            // 最轻的能配上最重的，就让它们一组（这样最重的不会浪费）
            l++;
            r--;
            ans++;
        } else {
            // 最重的配谁都超重（连最轻的都配不上），只能自己一组
            r--;
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 循环写成 while(l < r)：中间剩下的单独一件会被漏掉，答案偏小。
• 忘记 l == r 的特判：会变成「自己和自己配对」。
• 贪心策略选错：比如「贵的配贵的」（第 2 节的反例 A 就是它），或者「轻的配轻的」——都会错。
• 输入格式：w 在第一行、n 在第二行，然后 n 行每行一个价格。不要连续读成「一行两个数」，虽然用 cin >> 读其实都能过，但要看清题面。
• 以为一件纪念品可能超过 w：题目保证了 Pᵢ ≤ w，所以不用写「放不下就输出无解」那种逻辑。

题意：你和一堆石头，第 i 块高 hᵢ，地面高度 h₀ = 0。 从高度 x 跳到高度 y 消耗体力 (x − y)²。你必须把每块石头都跳一遍，最后停在哪块都行 （但不能跳回地面）。问：最多能消耗多少体力？

思路

这题要的是最大体力，而体力是「高度差的平方」。平方这个东西有个特点：

贪心策略：

1. 把高度从小到大排好序。
2. 从地面（高度 0）出发，先跳到最高的那块石头。
3. 然后跳到最矮的那块。
4. 再跳到第二高的，再跳到第二矮的……像拉锯齿一样在两端之间来回横跳。

为什么每步都跳到两端之一？因为排好序之后，离当前点最远的那个高度，一定在两端。 既然越远越耗体力，那一端必然是候选。

为什么是「交替」而不是「一直跳最高」？因为你不能跳回地面，也不能重复跳同一块石头。 跳到最高处之后再想跳远，就只能去最矮处；到了最矮处再想跳远，就只能回高处 —— 自然就形成了交替。

2
2 1

5

3
6 3 5

49

样例 1：地面 → 2（耗 2²=4）→ 1（耗 (2−1)²=1），共 5。
样例 2：排序后是 3 5 6。地面 → 6（耗 36）→ 3（耗 (6−3)²=9）→ 5（耗 (5−3)²=4），共 49。

完整代码

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

int h[305];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);          // 从小到大排好，方便从两端交替取

    long long ans = 0;       // ★ 答案能到 3×10^10，必须 long long
    int l = 0, r = n - 1;
    long long cur = 0;       // 当前位置的高度，一开始站在地上 h0 = 0
    bool takeRight = true;   // 先跳最高的

    while(l <= r){
        long long nxt;
        if(takeRight){
            nxt = h[r];      // 拿当前最高的
            r--;
        } else {
            nxt = h[l];      // 拿当前最矮的
            l++;
        }
        ans += (nxt - cur) * (nxt - cur);   // 消耗 (差值)²
        cur = nxt;
        takeRight = !takeRight;             // ★ 下一次换成另一端
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 用 int 存答案：最大能到 3×10¹⁰，必爆。这是本题最容易丢分的地方。
• 算平方时没转 long long：h[r] - h[l] 是 int，两个 int 相乘还是 int。
  本文代码里 nxt 和 cur 都声明成了 long long，所以自动就按 64 位算了。
• 跳跃方向搞反：题目要的是最大体力，不是最小。别习惯性地求最小。
• 忘了从地面出发：第一跳是从高度 0 起跳的，不是从某块石头起跳。cur 的初值必须是 0。
• 最后停在原地不动：题目说得很清楚，必须每块石头都跳到，不能跳过某些石头。所以循环必须在 l <= r 里把每一个都取走。
• 不能跳回地面：所以最后一步一定是停在某块石头上，不能加一步「跳回地面」。

题意：n 个糖果盒排成一排，第 i 盒有 aᵢ 颗糖。每次可以从某一盒里吃掉一颗。 目标是让任意两个相邻盒子的糖果数之和都不超过 x。问最少要吃几颗。

思路

从左往右一盒一盒地看。看第 i−1 盒和第 i 盒的时候，如果它俩的和超了 x， 那多出来的部分必须被吃掉，没得商量（因为只有这两盒能改，前面已经处理完了，不能反悔）。

问题只在于：吃哪一盒？

⚠️ 反例：无脑「只削右边」是错的

计划原文的提示是「一旦相邻两堆之和超过 x 就削掉右边的」。如果真的一行照抄，会挂在这组数据上：

3 2
4 1 3

4

无脑削右边：4 + 1 = 5 > 2，超出 3 颗，从第 2 盒削 3 颗 —— 可第 2 盒只有 1 颗，削完变成 −2，程序算出 3。
正确方案：第 1 盒吃 2 颗（4→2），第 2 盒吃 1 颗（1→0），第 3 盒吃 1 颗（3→2），共 4 颗。

我实际把两种版本都编译运行过：错误的版本在这组数据上输出 3， 暴力枚举版本输出 4。所以这个补丁是必需的，不是可写可不写。

为什么这样贪是对的

每一步我们处理的都是「当前这一对 (i−1, i)」。此时第 i−2 盒及更左边都已经合法了， 后面的盒子还没被这对影响。所以：

• 超出 x 的那部分无论如何都要吃掉（不在这两盒吃，就没别的地方可吃了）。
• 在这两盒里，吃第 i 盒（右边）永远不比吃第 i−1 盒差：因为减少第 i 盒只会让它更小， 待会儿处理 (i, i+1) 时更容易达标；而减少第 i−1 盒对未来的配对毫无帮助。
• 所以「能吃右边就吃右边」是安全的；只有右边不够时，才不得不往左边借。

注意吃左边也不会破坏已经处理好的部分：第 i−1 盒变小， a[i−2] + a[i−1] 只会更小，之前那个约束依然满足。

3 3
2 2 2

1

6 1
1 6 1 2 0 4

11

5 9
3 1 4 1 5

0

样例 1：2+2 = 4 > 3，吃掉 1 颗 → 1。
样例 2：第 2 盒吃 6 颗、第 4 盒吃 2 颗、第 6 盒吃 3 颗，共 11。
样例 3：所有相邻和分别是 4、5、5、6，都不超过 9，一颗都不用吃 → 0。

完整代码

#include <iostream>
using namespace std;

long long a[100005];            // ★ aᵢ 最大 10^9，且相邻和会用到两个数相加

int main(){
    ios::sync_with_stdio(false);    // n 最大 10^5，加快读入
    cin.tie(0);

    int n;
    long long x;
    cin >> n >> x;
    for(int i = 0; i < n; i++) cin >> a[i];

    long long eaten = 0;            // ★ 答案最大 10^14，必须 long long
    for(int i = 1; i < n; i++){
        long long sum = a[i - 1] + a[i];
        if(sum > x){
            // 至少要吃掉这么多颗，才能让 (i-1, i) 这一对和不超标
            long long need = sum - x;
            if(a[i] >= need){
                // 右盒够吃：全从右盒吃（右盒以后还能再削，最划算）
                a[i] -= need;
            } else {
                // ★ 右盒不够吃！先把右盒吃空，剩下不够的从上一盒补
                long long rest = need - a[i];
                a[i] = 0;
                a[i - 1] -= rest;   // rest ≤ a[i-1]，绝不会吃成负数
            }
            eaten += need;
        }
    }
    cout << eaten << "\n";
    return 0;
}

易错点

• 只削右边忘了补锅：右盒不够吃时会吃成负数，答案偏小。这是本题最大的坑。
• 用 int：aᵢ 能到 10⁹，两个相加就 2×10⁹ 已经爆 int；答案能到 10¹⁴，更是必须 long long。
• 从右往左扫：那样会破坏「左边已经处理好、永不回头」的不变量，方向必须是从左到右。
• 忘了 x 可以是 0：x = 0 时每一对相邻和都必须 ≤ 0，因为糖果数非负，所以最终所有盒子都得是 0。
• 以为要排序：这题不能排序！盒子是按位置排的，「相邻」指的是原来的位置关系，排完序就全乱了。