洛谷 P1223 排队接水

// P1223 错法一：比较器**只比接水时间** —— 并列时编号顺序不保证
//
// ★★★ 这是这一页的主角，也是这道题最隐蔽的一个 bug：
//   题面白纸黑字写着「**如果两个人接水的时间相同，编号更小的人应当排在前面**」，
//   而 `std::sort` **不是稳定排序** —— 比较器说「这两个不分先后」时，
//   它把谁放前面是没有承诺的。
//
// ⚠ 而它的抓获率有**两个主语**，页面第 ④ 步各量了一条曲线：
//   ① **值域**：`t` 的取值范围决定了「有没有并列」。没有并列，这个 bug 根本不存在。
//   ② ★★★ **n**：libstdc++ 的 `std::sort` 对**小数组直接走插入排序**（阈值 16），
//      而插入排序恰好是稳定的 ⇒ **n ≤ 16 时这个 bug 是精确的 0**。
//      官方样例 n = 10（而且里面真有一对并列的 99）—— **正好放过**。
//
// ⇒ 这是本书「小数据本身就是覆盖能力」（第 6 章 P8218）那条经验的一个**干净反例**：
//   这个 bug 只在数据**大**的时候才现形。两条经验都对，主语不一样。
//
// 修法有三种，随便挑一种：① 排 `pair` 用默认比较（正解那样）；
//   ② 比较器写全 `x.t != y.t ? x.t < y.t : x.id < y.id`；③ 换 `stable_sort`。

#include <bits/stdc++.h>
using namespace std;

struct P { int t, id; };

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<P> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].t; a[i].id = i + 1; }

    sort(a.begin(), a.end(), [](const P& x, const P& y) { return x.t < y.t; });   // ← 只比时间

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - 1 - i) * a[i].t;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].id, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

// P1223 错法二：总等待时间用 `int`
//
// 顶格 `n = 1000`、`t = 10⁶`：总等待最大 `10⁶ × 1000 × 999 / 2 ≈ 5.0 × 10¹¹`，
// 而 `int` 只到 2 147 483 647 —— 差了两百多倍。
//
// ★ 而这一条正是第 19 章正文第 ⑦ 步那个警告框说的事，那儿写着
//   「**对拍永远不会告诉你这件事** …… 这只能靠脑子」。
//   ⚠ **在这道题上那句话不成立**（页面第 ⑤ 步实测）：那句话的隐含前提是
//   「参照物是暴力」（第 11 章 P1908 已经把这个主语点出来了）——
//   而这道题的参照物**就是正解本身，只换了一个类型**，顶格随便跑。
//
// ⇒ 顶格档（n = 1000, t ≤ 10⁶）对拍，它**每一轮都被抓**。
//   ⚠ 官方样例（n = 10，总等待 2919）当然放过它。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    int total = 0;                                   // ← 这里
    for (int i = 0; i < n; i++) total += (n - 1 - i) * a[i].first;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

// P1223 错法三：把「自己的接水时间」也算进等待
//
// 题面特意写了一句：「**一个人的等待时间不包括他的接水时间**。」
// 这句提醒按第 12 章那套分法是**命门**（不是情报、也不是噪声）：
//   照着「等待 = 轮到我之前的全部时间 + 我自己接水」写，系数就从 `n-1-i` 变成 `n-i`，
//   答案每一组都会多出 `sum(t) / n`。
//
// ★ 它错得非常显眼 —— **官方样例当场就挡住了**（532.00 vs 291.90）。
//   ⇒ 和上面两个错法凑成这一页的一条观察：
//     **官方样例挡住的都是「每一组都错」的，放过的都是「偶尔才错」的。**
//     这不是运气，几乎是必然：样例只有一组，它天生就是一个「一测就死」的过滤器。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - i) * a[i].first;   // ← n-i，多算了自己

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

// P1223 错法四：平均值用**整数除法**
//
// `total / n` 先把小数截掉了，再交给 `%.2f` —— 打出来永远是 `xxx.00`。
// 官方样例：2919 / 10 = 291 ⇒ `291.00`，而答案是 `291.90`。**样例当场挡住。**
//
// ★ 留着它是为了凑齐这一页那张「样例挡不挡得住」的表：
//   四个错法里，样例挡住的两个都是「每一组都错」的，放过的两个都是「偶尔才错」的。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i + 1; }
    sort(a.begin(), a.end());

    long long total = 0;
    for (int i = 0; i < n; i++) total += (long long)(n - 1 - i) * a[i].first;

    for (int i = 0; i < n; i++) printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)(total / n));      // ← 括号位置：整数除完才转 double
    return 0;
}

// P1223 排队接水 —— ★ 这一版就能 AC
//
// ★★★ 这道题的算法，第 19 章正文已经**证完了**：
//   按接水时间从小到大排，交换论证两行推导（见 /ch/19-greedy-sorting/ 第 ⑤ 步）。
//   ⇒ 写这道题的算法部分只要三分钟：`sort` 一句，累加一句。
//
// 而它能不能 AC，全押在**三件和贪心毫无关系的事**上（页面第 ③ ④ ⑤ 步各量了一件）：
//   ① 要输出的是**编号**不是时间 —— 所以排的是 `(时间, 编号)` 这个 pair；
//   ② 题面那句「**接水时间相同，编号更小的排在前面**」是**命门**：
//      比较器只比时间的话，`std::sort` 不保证并列元素的相对顺序（它不是稳定排序）；
//      ⚠ 而这个 bug **在 n ≤ 16 时抓不到**（libstdc++ 小数组直接走插入排序），
//        官方样例 n = 10 —— 正好放过；
//   ③ 总等待时间要开 **long long**：顶格 `n = 1000`、`t = 10⁶` 时约 5 × 10¹¹。
//
// ★ 第 ② 条这里是**白拿**的：`pair` 的默认比较就是「先比 first，再比 second」，
//   而我们把编号放在 second —— 题面要的 tie-break 一个字都不用写。
//
// 输出：第一行是排队顺序（编号），第二行是平均等待时间，保留两位小数。
//   ⚠ 平均要用**浮点**除（`(double)total / n`），整数除法当场就错（样例挡得住这一个）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<pair<int, int>> a(n);             // (接水时间, 编号)
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a.begin(), a.end());                // ★ 默认比较 = 先按时间，时间相同按编号

    long long total = 0;                     // ★ 顶格约 5e11，int 装不下
    for (int i = 0; i < n; i++)
        total += (long long)(n - 1 - i) * a[i].first;   // 排第 i+1 位的人，被后面 n-1-i 个人等

    for (int i = 0; i < n; i++)
        printf("%d%c", a[i].second, i + 1 == n ? '\n' : ' ');
    printf("%.2f\n", (double)total / n);
    return 0;
}

// P1223 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1223Count`      人看的版本
// `./p1223Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 六段：
//   ① ★ 升序真的最优吗：小 n 全排列穷举，和「排序后累加」逐组比；
//   ② ★★ `int` 的**精确分界**：全 t = 10⁶ 时，最小的会溢出的 n（算术题，不用测）；
//   ③ ★★★ `std::sort` 的**稳定性分界**：全部元素相等时，最小的会打乱编号顺序的 n
//      （libstdc++ 小数组走插入排序 —— 这是**实现细节**，所以要量不要背）；
//   ④ ★★★ 「只比时间」那个 bug 的 **n 曲线**（值域固定为 5，保证有并列 ⇒ 只剩 n 这一个变量）；
//   ⑤ ★★ 它的**值域曲线**（n 固定 1000）—— 抓获率的第一个主语是「有没有并列」；
//   ⑥ ★★ `int` 版的 n 曲线，以及**随机数据**下它开始出错的最小 n
//      （⚠ 和第 ② 段那条算出来的线**不是一回事**：一个是最坏，一个是随机）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

struct P { int t, id; };

/** 正解：排 (时间, 编号)，返回排好的编号序列 + 总等待 */
static void solve(const vector<int>& t, vector<int>& order, ll& total) {
    int n = t.size();
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) a[i] = {t[i], i + 1};
    sort(a.begin(), a.end());
    order.clear();
    total = 0;
    for (int i = 0; i < n; i++) {
        order.push_back(a[i].second);
        total += (ll)(n - 1 - i) * a[i].first;
    }
}

/** 错法一：比较器只比时间 */
static void solveCmp(const vector<int>& t, vector<int>& order) {
    int n = t.size();
    vector<P> a(n);
    for (int i = 0; i < n; i++) a[i] = {t[i], i + 1};
    sort(a.begin(), a.end(), [](const P& x, const P& y) { return x.t < y.t; });
    order.clear();
    for (int i = 0; i < n; i++) order.push_back(a[i].id);
}

/** 错法二：总等待用 int 累加（这里真的用 int 加一遍，好把溢出行为原样复现） */
static int solveInt(const vector<int>& t) {
    int n = t.size();
    vector<int> s = t;
    sort(s.begin(), s.end());
    int total = 0;
    for (int i = 0; i < n; i++) total += (n - 1 - i) * s[i];
    return total;
}

static vector<int> gen(mt19937& rng, int n, int hi) {
    vector<int> t(n);
    for (int i = 0; i < n; i++) t[i] = rng() % (unsigned)hi + 1;
    return t;
}
static bool hasDup(vector<int> t) {
    sort(t.begin(), t.end());
    return adjacent_find(t.begin(), t.end()) != t.end();
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 升序真的最优吗 —— 小 n 全排列穷举 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int n = 1; n <= 8; n++) {
            for (int rep = 0; rep < 40; rep++, groups++) {
                vector<int> t = gen(rng, n, 20);
                vector<int> idx(n);
                iota(idx.begin(), idx.end(), 0);
                ll best = LLONG_MAX;
                do {
                    ll s = 0;
                    for (int i = 0; i < n; i++) s += (ll)(n - 1 - i) * t[idx[i]];
                    best = min(best, s);
                } while (next_permutation(idx.begin(), idx.end()));
                vector<int> ord; ll total;
                solve(t, ord, total);
                if (total != best) bad++;
            }
        }
        if (!CSV) printf("① 全排列穷举 %d 组（n <= 8）：排序贪心和最优解不一致 %d 组\n", groups, bad);
        row("opt", {groups, bad});
    }

    /* ② int 的精确分界：全 t = 10^6 时最小的溢出 n */
    {
        const ll T = 1000000;
        int lim = -1;
        for (int n = 1; n <= 1000; n++) {
            ll total = T * n * (n - 1) / 2;         // 全部相等时的总等待
            if (total > 2147483647LL) { lim = n; break; }
        }
        ll below = T * (ll)(lim - 1) * (lim - 2) / 2, at = T * (ll)lim * (lim - 1) / 2;
        ll top = T * 1000LL * 999LL / 2;
        if (!CSV) printf("② 全 t = 10^6：n = %d 总等待 %lld（< 2^31），n = %d 是 %lld（>= 2^31）；顶格 n = 1000 是 %lld\n",
                         lim - 1, below, lim, at, top);
        row("bound", {lim, below, at, top});
    }

    /* ③ std::sort 的稳定性分界：全部元素相等，最小的会打乱编号的 n */
    {
        int lim = -1;
        for (int n = 1; n <= 200 && lim < 0; n++) {
            vector<int> t(n, 7);
            vector<int> ord;
            solveCmp(t, ord);
            for (int i = 0; i < n; i++) if (ord[i] != i + 1) { lim = n; break; }
        }
        vector<int> t17(lim, 7), ord17;
        solveCmp(t17, ord17);
        int moved = 0;
        for (int i = 0; i < lim; i++) if (ord17[i] != i + 1) moved++;
        if (!CSV) printf("③ 全部相等：n <= %d 时 std::sort 保持编号升序，n = %d 起被打乱（那一档有 %d 个位置错位）\n",
                         lim - 1, lim, moved);
        row("stable", {lim, moved});
    }

    /* ④ 「只比时间」的 n 曲线（值域固定 5 ⇒ 必有并列） */
    {
        const int NS[] = {4, 8, 16, 17, 20, 32, 100, 1000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 7919u + 11u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 5);
                vector<int> a, b; ll total;
                solve(t, a, total);
                solveCmp(t, b);
                if (a != b) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("④ n = %4d（t <= 5）：只比时间那版错 %d / 300\n", n, bad);
        }
        row("cmpN", out);
    }

    /* ⑤ 它的值域曲线（n 固定 1000） */
    {
        const int HIS[] = {5, 100, 10000, 1000000};
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 2654435761u + 3u);
            int bad = 0, dup = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, 1000, hi);
                if (hasDup(t)) dup++;
                vector<int> a, b; ll total;
                solve(t, a, total);
                solveCmp(t, b);
                if (a != b) bad++;
            }
            out.push_back(bad); out.push_back(dup);
            if (!CSV) printf("⑤ n = 1000，t <= %7d：只比时间那版错 %d / 300，其中含并列的输入 %d / 300\n", hi, bad, dup);
        }
        row("cmpHi", out);
    }

    /* ⑥ int 版的 n 曲线 + 随机数据下的实际分界 */
    {
        const int NS[] = {8, 50, 65, 66, 100, 1000};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 40503u + 7u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                if ((ll)solveInt(t) != total) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("⑥ n = %4d（t <= 10^6）：int 版错 %d / 300\n", n, bad);
        }
        int firstAll = -1, firstAny = -1;
        for (int n = 2; n <= 300; n++) {
            mt19937 rng(n * 40503u + 7u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                if ((ll)solveInt(t) != total) bad++;
            }
            if (bad > 0 && firstAny < 0) firstAny = n;
            if (bad == 300) { firstAll = n; break; }
        }
        if (!CSV) printf("⑥ 随机 t <= 10^6：int 版第一次出错在 n = %d，到 n = %d 起 300 轮全错\n", firstAny, firstAll);
        out.push_back(firstAny); out.push_back(firstAll);
        row("intN", out);
    }

    /* ⑦ ★★★ 为什么随机数据的溢出线比算出来的那条晚一倍：**排序本身把总等待压小了三倍**
       升序排好之后，大系数 `n-1-i` 配到的是**小**的那些 t。
       随机均匀的 t 排序后 `E[s_i] ≈ (i+1)/(n+1)·T`，代进去：
         E[总等待] = Σ (n-1-i)·(i+1)/(n+1)·T = T·n(n-1)/6
       而全部 t 都顶格时是 `T·n(n-1)/2` —— **正好 3 倍**。这一段实测那个 3。 */
    {
        const int NS2[] = {100, 1000};
        vector<ll> out;
        for (int n : NS2) {
            mt19937 rng(n * 99991u + 5u);
            long double sum = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, n, 1000000);
                vector<int> ord; ll total;
                solve(t, ord, total);
                sum += (long double)total;
            }
            ll avg = (ll)(sum / 300 + 0.5L);
            ll worst = 1000000LL * n * (n - 1) / 2;
            ll ratio100 = (ll)((long double)worst / (long double)avg * 100 + 0.5L);
            out.push_back(avg); out.push_back(worst); out.push_back(ratio100);
            if (!CSV) printf("⑦ n = %4d：随机数据平均总等待 %lld，全部顶格 %lld，比值 %.2f\n",
                             n, avg, worst, ratio100 / 100.0);
        }
        row("ratio", out);
    }
    return 0;
}

// P1223 对拍生成器：`./p1223Gen <seed> [n] [t 的上限]`
//   默认 `n = 1000`、`t ≤ 10⁶` —— ★ **就是题面的顶格档**。
//
// ★ 默认值写成顶格是有意的（本书第 53 条经验：生成器的默认档位要写成最终档）。
//   这道题的两个隐蔽 bug 恰好各要一头：
//     · `int` 溢出要 **n 和 t 都大**（顶格必炸，页面第 ⑤ 步算得出精确分界 n = 66）；
//     · 排序不稳定要 **n > 16**（小数组走插入排序）**且值域小到有并列**。
//   ⇒ 顺手写的 `n ≤ 10`、`t ≤ 100` 那种生成器，**两个都是精确的 0**。
//
// 值域这个旋钮单独拎出来（页面第 ④ 步那张表就是拧它拧出来的）：
//   `t` 的上限越小，并列越多，「只比时间」那个 bug 越容易现形。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int n = argc > 2 ? atoi(argv[2]) : 1000;
    int hi = argc > 3 ? atoi(argv[3]) : 1000000;
    n = max(1, min(1000, n));
    hi = max(1, min(1000000, hi));

    mt19937 rng(seed * 2654435761u + 12345u);
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%u%c", (unsigned)(rng() % (unsigned)hi) + 1, i + 1 == n ? '\n' : ' ');
    return 0;
}