洛谷 P1068 [NOIP 2009 普及组] 分数线划定

// P1068 分数线划定 —— ★ 这一版就能 AC
//
// 三件事，缺一不可：
//   ① 分数线 = 排名第 `⌊m × 150%⌋` 名那个人的**分数**；
//   ② 最终进面试的是**所有分数 >= 分数线**的人 —— 人数可能比 ⌊1.5m⌋ **多**
//      （样例就是：算出来 4 个，因为第 4 名那个 88 分有并列，最后 5 个人进）；
//   ③ 排序是**双关键字**：成绩从高到低，成绩相同时报名号从小到大。
//
// ⚠ 第 ② 条是这道题的全部难点，而它在样例里就写着 —— **样例说明专门解释了这件事**。
//   ⇒ 又一次「第一步永远是把样例读完」（第 8 章 P2249 那页那条）。
//
// ★ `m * 3 / 2` 和 `(int)(m * 1.5)` 在这道题上**完全等价**，一次都不会差
//   —— 网上常见的那条「别用 1.5，会掉精度」的提醒，主语错了，见 p1068Count.cpp。

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

struct Player { int id, score; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Player> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;

    sort(v.begin(), v.end(), [](const Player& a, const Player& b) {
        if (a.score != b.score) return a.score > b.score;    // 成绩高的在前
        return a.id < b.id;                                  // ③ 成绩相同，报名号小的在前
    });

    int line = v[m * 3 / 2 - 1].score;                       // ① 第 ⌊1.5m⌋ 名的分数（下标从 0 起）
    int cnt = 0;
    while (cnt < n && v[cnt].score >= line) cnt++;           // ② 所有 >= 分数线的都算

    cout << line << ' ' << cnt << '\n';
    for (int i = 0; i < cnt; i++) cout << v[i].id << ' ' << v[i].score << '\n';
    return 0;
}

// ⚠ 故意写错的：只取前 ⌊m × 150%⌋ 名，没管并列
//
//     int cnt = m * 3 / 2;      ← 正解还要往后走，把所有「分数 >= 分数线」的都收进来
//
// ★ 它**样例就挂**：样例算出来分数线是 88、名额 4 个，
//   可 88 分有两个人（1001 和 3239），题面明说这两个都进 ⇒ 正确答案是 **5** 个人。
//
// ⚠ 值得注意的是它错得**很轻**：分数线那个数是对的，前 4 行也一字不差，
//   只是少了最后一行、而且人数少了 1。
//   ⇒ 这种「只差一行」的错，肉眼扫一遍输出很容易放过去 —— 逐字节比才看得出来。

#include <bits/stdc++.h>
using namespace std;
struct Player { int id, score; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Player> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;
    sort(v.begin(), v.end(), [](const Player& a, const Player& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    });
    int cnt = m * 3 / 2;                                     // ⚠ 就是这一行
    int line = v[cnt - 1].score;
    cout << line << ' ' << cnt << '\n';
    for (int i = 0; i < cnt; i++) cout << v[i].id << ' ' << v[i].score << '\n';
    return 0;
}

// ⚠ 故意写错的：cmp 只写了成绩，漏掉第二关键字（报名号）
//
//     return a.score > b.score;     ← 成绩相同时，谁在前面就**不确定**了
//
// ★ 这一版的诡异之处：它**不一定错**。`std::sort` 不保证稳定，
//   但也没规定并列的一定会乱 —— 数据小的时候常常「碰巧」是对的。
//   ⇒ 于是它是那种「本地样例过了、交上去 WA」的典型。
//
// ⚠ 更要命的是：**换一台机器、换一个编译器版本，它的输出可能就变了**
//   （`sort` 的实现细节不同）。⇒ 这类 bug 连「复现」都不保证。
//
// ★ 抓它要靠**大量同分**的数据（见 p1068Gen.cpp 的档位 1）。

#include <bits/stdc++.h>
using namespace std;
struct Player { int id, score; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Player> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].id >> v[i].score;
    sort(v.begin(), v.end(), [](const Player& a, const Player& b) {
        return a.score > b.score;                            // ⚠ 少了 id 那一句
    });
    int line = v[m * 3 / 2 - 1].score;
    int cnt = 0;
    while (cnt < n && v[cnt].score >= line) cnt++;
    cout << line << ' ' << cnt << '\n';
    for (int i = 0; i < cnt; i++) cout << v[i].id << ' ' << v[i].score << '\n';
    return 0;
}

// 「别用 1.5，会掉精度」—— 这条提醒到底对不对？扫一遍
//
// 用法：./p1068Count          人话版
//       ./p1068Count csv      只打 `键,值`，给 check:viz 用
//
// 网上题解常见的提醒是：「`m * 150%` 要写成 `m * 3 / 2`，别写 `(int)(m * 1.5)`，
// 浮点会掉精度」。听起来很有道理 —— **但这道题上它一次都不会错**。
//
// 这份程序做两件事：
//   ① 在题面的范围 `m ∈ [3, 5000]` 里，把三种写法逐个比过去；
//   ② 换几个别的倍数做对照，看「掉精度」到底什么时候真的发生。
//
// ★ 结论先写在这儿（下面是跑出来的）：**危险的不是「用了浮点」，
//   是「那个小数在二进制里做乘法之后，会不会正好跨过一个整数边界」** ——
//   而这既不等于「是不是有限二进制小数」，也不能靠直觉，只能算或者扫。

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

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

    /* ① 题面范围内的三种写法 */
    int bad = 0, firstBad = -1;
    for (int m = 3; m <= 5000; m++) {
        int a = (int)(m * 1.5), b = m * 3 / 2, c = m * 150 / 100;
        if (a != b || b != c) { bad++; if (firstBad < 0) firstBad = m; }
    }

    /* ② 对照：几个不同的倍数，各在 [1, 10⁶] 里错多少次 */
    struct Case { const char* name; double f; long long num, den; };
    Case cs[] = {
        { "1.5", 1.5, 3, 2 }, { "1.25", 1.25, 5, 4 },
        { "1.1", 1.1, 11, 10 }, { "0.9", 0.9, 9, 10 }, { "0.7", 0.7, 7, 10 },
    };
    long long cnt[5]; long long first[5];
    for (int i = 0; i < 5; i++) {
        cnt[i] = 0; first[i] = -1;
        for (long long m = 1; m <= 1000000; m++) {
            long long x = (long long)(m * cs[i].f), y = m * cs[i].num / cs[i].den;
            if (x != y) { cnt[i]++; if (first[i] < 0) first[i] = m; }
        }
    }

    if (csv) {
        printf("inRange,%d\n", bad);
        for (int i = 0; i < 5; i++) printf("bad_%s,%lld\nfirst_%s,%lld\n", cs[i].name, cnt[i], cs[i].name, first[i]);
        return 0;
    }
    printf("① 题面范围 m ∈ [3, 5000]：(int)(m*1.5) / m*3/2 / m*150/100 三者不一致 **%d** 次\n", bad);
    printf("   ⇒ 那条「别用 1.5」的提醒，在这道题上**一次都用不上**。\n\n");
    printf("② 换几个倍数，在 m ∈ [1, 10⁶] 里各错多少次：\n\n");
    for (int i = 0; i < 5; i++) {
        printf("   ×%-5s 不一致 %8lld 次", cs[i].name, cnt[i]);
        if (first[i] > 0) printf("，第一个 m = %lld", first[i]);
        printf("\n");
    }
    printf("\n   ★ 1.5 和 1.25 是**二进制精确**的（3/2、5/4）—— 乘出来一位不差，当然不会错。\n");
    printf("   ★★ 可 1.1 和 0.9 **并不精确**，却也一次没错 —— 「不精确」不等于「会出事」。\n");
    printf("   ★★★ 只有 0.7 真的错了，而且从 m = %lld 就开始。\n", first[4]);
    printf("   ⇒ 判断依据不是「是不是浮点」，也不是「精不精确」，\n");
    printf("     是「乘完之后会不会正好落在整数边界的另一侧」—— 这只能算，或者像这样扫一遍。\n");
    return 0;
}

// P1068 的对拍参照物：不用 sort，用**选择排序**自己排一遍
//
// ★ 它和正解**没有共用任何一行排序代码** —— 正解用 `std::sort` + 自定义 cmp，
//   这里是最笨的双重循环，每次挑出「成绩最高、并列时报名号最小」的那个。
//   ⇒ 两边一起错的概率极低（第 7 章 P1147 那条：验算要走一条无关的路）。
//
// ⚠ 顺带：选择排序**不稳定**，但这里根本不需要稳定 ——
//   因为 cmp 已经把「成绩 + 报名号」定死了，任何两个人都分得出先后，
//   排出来的顺序是**唯一**的。⇒ 「要不要稳定排序」这个问题，
//   在「关键字能把所有元素两两分开」时根本不存在（P1104 那页才是它真的要紧的地方）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> id(n), sc(n);
    for (int i = 0; i < n; i++) cin >> id[i] >> sc[i];
    vector<bool> used(n, false);
    vector<int> ord;
    for (int k = 0; k < n; k++) {
        int best = -1;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (best < 0 || sc[i] > sc[best] || (sc[i] == sc[best] && id[i] < id[best])) best = i;
        }
        used[best] = true;
        ord.push_back(best);
    }
    int line = sc[ord[m * 3 / 2 - 1]];
    int cnt = 0;
    while (cnt < n && sc[ord[cnt]] >= line) cnt++;
    cout << line << ' ' << cnt << '\n';
    for (int i = 0; i < cnt; i++) cout << id[ord[i]] << ' ' << sc[ord[i]] << '\n';
    return 0;
}

// 数据生成器（P1068 对拍用）：`./p1068Gen <seed> [level]`
//
//   level 0（默认）成绩随机取 [1,100] —— 兜底
//   level 1        ★ **大量同分**：成绩只在 3 个值里取
//                  ⇒ 专抓 p1068NoTie（cmp 漏了报名号）和 p1068Cut（没算并列）
//   level 2        ★ **分数线上正好有一堆并列**：先随机造，再把第 ⌊1.5m⌋ 名前后的分数抹平
//                  ⇒ 专抓 p1068Cut
//
// ⚠ 题面：5 <= n <= 5000，3 <= m <= n，报名号 k ∈ [1000, 9999] 且**互不相同**，
//   成绩 s ∈ [1, 100]，并且保证 ⌊1.5m⌋ <= n。
//   ★ 报名号互不相同这一条必须守住 —— 否则「并列时按报名号排」就没有唯一答案了，
//     两个程序会「一致地输出垃圾」。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    int n = ri(5, 30);
    int m = ri(3, max(3, (n * 2) / 3));                    // 保证 ⌊1.5m⌋ <= n
    while (m * 3 / 2 > n) m--;

    /* 报名号互不相同 */
    vector<int> ids;
    {
        set<int> s;
        while ((int)s.size() < n) s.insert(ri(1000, 9999));
        ids.assign(s.begin(), s.end());
        for (int i = n - 1; i > 0; i--) swap(ids[i], ids[ri(0, i)]);
    }
    vector<int> sc(n);
    for (int i = 0; i < n; i++) sc[i] = (level == 1) ? ri(1, 3) * 10 : ri(1, 100);
    if (level == 2) {
        /* 把分数线附近抹平：先排个序找出第 ⌊1.5m⌋ 名的分数，再把一批人都设成它 */
        vector<int> t = sc;
        sort(t.rbegin(), t.rend());
        int line = t[m * 3 / 2 - 1];
        for (int i = 0; i < n; i++) if (ri(0, 2) == 0) sc[i] = line;
    }
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) printf("%d %d\n", ids[i], sc[i]);
    return 0;
}