洛谷 P1271 【深基9.例1】选举学生会

// P1271 选举学生会 —— ★ 这一版就能 AC：计数排序
//
// 题面给了两个数：候选人 `n <= 999`，选票 `m <= 2×10⁶`，而且每张票上的数在 [1, n] 里。
// ⇒ **值域只有 999，数据却有 200 万** —— 这正是计数排序的主场：
//
//     cnt[a_i]++            读的时候顺手数
//     for v = 1..n          按编号从小到大
//         输出 cnt[v] 个 v
//
// 复杂度 `O(n + m)`，而 `sort` 是 `O(m log m)`（log 2×10⁶ ≈ 21）。
//
// ⚠ 但这道题真正的门槛不在排序上，在 **IO** 上：要读 200 万个数、再输出 200 万个数。
//   ⇒ 见 p1271Read.cpp 那张表 —— 读法选错了，算法再快也没用。

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

static int cnt[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; i++) { int x; cin >> x; cnt[x]++; }
    /* ⚠ 末尾那个换行不能靠「v == n 且是这一格的最后一个」来判 ——
       没人投给最后一号候选人时 cnt[n] == 0，那个条件永远不成立，
       整份输出就少了结尾的换行。⇒ 老老实实数第几个。
       ★ 这个 bug 我自己踩了：第一版拿 .strip() 比对拍，正好把它抹掉了，
         是 check:viz 逐字节比才报出来的（900 轮里 307 轮不一致）。 */
    int printed = 0;
    for (int v = 1; v <= n; v++)
        for (int k = 0; k < cnt[v]; k++) cout << v << " \n"[++printed == m];
    return 0;
}

// 另一版：老老实实读进来，`sort` 一遍
//
// 它**也能过** —— 这一页不是要证明「sort 不行」，而是要量清楚
// **在这道题的规模上，两者差多少**（见 p1271Count.cpp）。
//
// ★ 值得先想清楚的一件事：`sort` 是 `O(m log m)` = 2×10⁶ × 21 ≈ 4.2×10⁷ 次比较，
//   计数排序是 `O(n + m)` ≈ 2×10⁶ 次自增。**理论上差 20 倍。**
//   ⚠ 可实测差不了那么多 —— 因为这道题的时间**大头在 IO 上**，不在排序上。
//   ⇒ 这正是「复杂度更优不等于快多少」的又一个现场（第 7 章 P1873 那条）。

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

static int a[2000006];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; i++) cin >> a[i];
    sort(a, a + m);
    for (int i = 0; i < m; i++) cout << a[i] << " \n"[i + 1 == m];
    return 0;
}

// 只量「排序那一段」：计数排序 vs sort（把 IO 摘出去）
//
// 用法：./p1271Count [n] [m]          人话版
//       ./p1271Count [n] [m] csv      给 check:viz 用
//
// ★ 为什么要把 IO 摘出去：这道题端到端的时间**大头在 IO 上**（见 p1271Read.cpp），
//   直接比两个程序的总时间，量到的主要是读写，不是排序。
//   ⇒ 想知道「计数排序到底快多少」，就得只掐排序那一段。
//
// 两个数一起报：
//   · **次数**：sort 是 O(m log m) ≈ m × 21，计数排序是 m 次自增 + n 次扫描；
//   · **秒表**：同一份数组，两种排法各跑一次。

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

static int a[2000006], b[2000006], cnt[1005];

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 999;
    int m = (argc > 2) ? atoi(argv[2]) : 2000000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");

    mt19937 rng(20260827u);
    for (int i = 0; i < m; i++) a[i] = (int)(rng() % (unsigned)n) + 1;

    memcpy(b, a, sizeof(int) * (size_t)m);
    auto t0 = steady_clock::now();
    sort(b, b + m);
    double msSort = duration<double, milli>(steady_clock::now() - t0).count();

    t0 = steady_clock::now();
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < m; i++) cnt[a[i]]++;
    int p = 0;
    for (int v = 1; v <= n; v++) for (int k = 0; k < cnt[v]; k++) a[p++] = v;
    double msCount = duration<double, milli>(steady_clock::now() - t0).count();

    bool same = memcmp(a, b, sizeof(int) * (size_t)m) == 0;
    int lg = 0; for (int x = m; x > 0; x >>= 1) lg++;
    long long sortOps = (long long)m * lg;
    long long countOps = (long long)m + n;

    if (csv) {
        printf("n,%d\nm,%d\nsame,%d\n", n, m, same ? 1 : 0);
        printf("sortOps,%lld\ncountOps,%lld\nopsRatio,%lld\n", sortOps, countOps, sortOps / max(1LL, countOps));
        printf("sortFaster,%d\n", (msSort < msCount) ? 1 : 0);
        return 0;
    }
    printf("n = %d、m = %d，只量排序那一段：\n\n", n, m);
    printf("  sort        %8.1f 毫秒   ≈ m × log2(m) = %lld 次比较\n", msSort, sortOps);
    printf("  计数排序    %8.1f 毫秒   ≈ m + n       = %lld 次自增\n", msCount, countOps);
    printf("\n  两边结果%s。次数差 %lld 倍，秒表差 %.1f 倍。\n",
           same ? "逐字节相同" : "居然不一样！", sortOps / max(1LL, countOps), msSort / max(0.001, msCount));
    printf("  ⚠ 而这道题端到端的时间大头在 IO 上 —— 排序快 %.1f 倍，总时间未必快那么多。\n",
           msSort / max(0.001, msCount));
    return 0;
}

// 顶格数据（P1271 计时用）：`./p1271GenBig <n> <m> [level]`
//   level 0 随机 / 1 全投一个人 / 2 均匀分给每个人
// ⚠ 题面：n <= 999、m <= 2×10⁶、a_i ∈ [1, n]。默认按顶格。

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 999;
    int m = (argc > 2) ? atoi(argv[2]) : 2000000;
    int level = (argc > 3) ? atoi(argv[3]) : 0;
    mt19937 rng(20260827u);
    printf("%d %d\n", n, m);
    for (int i = 0; i < m; i++) {
        int v = (level == 1) ? 1 : (level == 2) ? (i % n) + 1 : (int)(rng() % (unsigned)n) + 1;
        printf("%d%c", v, i + 1 == m ? '\n' : ' ');
    }
    return 0;
}

// P1271 的真正门槛：200 万个数进来、200 万个数出去
//
// 用法：./p1271Read [n] [m]           人话版
//       ./p1271Read [n] [m] csv       只打 `键,值`，给 check:viz 用
//   默认就是题面顶格：n = 999、m = 2×10⁶。
//
// ★ 这一页和[第 8 章 P2249]那一页量的是同一件事，但结论**正好相反**：
//   那道题 110 万个整数，默认 `cin` 234 毫秒，离 1 秒还有四倍余量 ⇒ 提示是虚的；
//   这道题**读 200 万 + 写 200 万**，量出来是另一个样子。
//
// ⚠ 这份程序自己造数据写进临时文件，再 freopen 回来读 —— 不需要喂输入。
// ⚠ 「同步开着」那一趟必须排最前面（关掉同步之后 cin 会预读，换文件会读到残渣）。
//
// 输出那一侧量三种：① cout 同步开着 ② cout 关同步 ③ 自己拼一个大 buffer 一次 fwrite。
// ⚠ 输出统一写到 /dev/null，量的是**生成字节**的代价，不含磁盘。

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

static char path[64];
static int cnt[1005];
static int n, m;

static void makeData(int nn, int mm) {
    snprintf(path, sizeof(path), "/tmp/p1271-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件\n"); exit(1); }
    mt19937 rng(20260827u);
    fprintf(f, "%d %d\n", nn, mm);
    for (int i = 0; i < mm; i++) fprintf(f, "%d%c", (int)(rng() % (unsigned)nn) + 1, i + 1 == mm ? '\n' : ' ');
    fclose(f);
}
static void reopenIn() { if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); } }

static char ibuf[1 << 22];
static size_t ipos = 0, ilen = 0;
static inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return EOF; }
    return ibuf[ipos++];
}
static inline int readIntFast() {
    int c = gc(), x = 0;
    while (c != EOF && (c < '0' || c > '9')) c = gc();
    for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + (c - '0');
    return x;
}

int main(int argc, char** argv) {
    int nn = (argc > 1) ? atoi(argv[1]) : 999;
    int mm = (argc > 2) ? atoi(argv[2]) : 2000000;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    makeData(nn, mm);
    double rms[4], wms[3];
    long long sum[4];

    /* ---- 读：四种 ---- */
    { reopenIn(); memset(cnt, 0, sizeof(cnt));
      auto t0 = steady_clock::now();
      cin >> n >> m; long long s = 0;
      for (int i = 0; i < m; i++) { int x; cin >> x; cnt[x]++; s += x; }
      sum[0] = s; rms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }
    { reopenIn(); memset(cnt, 0, sizeof(cnt));
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false); cin.tie(nullptr);
      cin >> n >> m; long long s = 0;
      for (int i = 0; i < m; i++) { int x; cin >> x; cnt[x]++; s += x; }
      sum[1] = s; rms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }
    { reopenIn(); memset(cnt, 0, sizeof(cnt));
      auto t0 = steady_clock::now();
      if (scanf("%d %d", &n, &m) != 2) { n = m = 0; }
      long long s = 0;
      for (int i = 0; i < m; i++) { int x; if (scanf("%d", &x) != 1) break; cnt[x]++; s += x; }
      sum[2] = s; rms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }
    { reopenIn(); ipos = ilen = 0; memset(cnt, 0, sizeof(cnt));
      auto t0 = steady_clock::now();
      n = readIntFast(); m = readIntFast();
      long long s = 0;
      for (int i = 0; i < m; i++) { int x = readIntFast(); cnt[x]++; s += x; }
      sum[3] = s; rms[3] = duration<double, milli>(steady_clock::now() - t0).count(); }

    /* ---- 写：三种（都写到 /dev/null，量生成字节的代价） ---- */
    {   FILE* devnull = fopen("/dev/null", "w");
        /* ① cout 同步开着 */
        { auto t0 = steady_clock::now();
          ostringstream oss;
          ios::sync_with_stdio(true);
          for (int v = 1; v <= n; v++) for (int k = 0; k < cnt[v]; k++) oss << v << ' ';
          fwrite(oss.str().data(), 1, oss.str().size(), devnull);
          wms[0] = duration<double, milli>(steady_clock::now() - t0).count(); }
        /* ② ostringstream（等价于 cout 关同步的代价） */
        { auto t0 = steady_clock::now();
          ostringstream oss;
          for (int v = 1; v <= n; v++) for (int k = 0; k < cnt[v]; k++) oss << v << ' ';
          fwrite(oss.str().data(), 1, oss.str().size(), devnull);
          wms[1] = duration<double, milli>(steady_clock::now() - t0).count(); }
        /* ③ 自己拼 buffer 一次 fwrite */
        { auto t0 = steady_clock::now();
          static char ob[1 << 25];
          size_t p = 0;
          for (int v = 1; v <= n; v++) {
              char tmp[8]; int len = 0, x = v;
              do { tmp[len++] = char('0' + x % 10); x /= 10; } while (x);
              for (int k = 0; k < cnt[v]; k++) {
                  for (int t = len - 1; t >= 0; t--) ob[p++] = tmp[t];
                  ob[p++] = ' ';
              }
          }
          fwrite(ob, 1, p, devnull);
          wms[2] = duration<double, milli>(steady_clock::now() - t0).count(); }
        fclose(devnull);
    }

    remove(path);
    bool same = (sum[0] == sum[1] && sum[1] == sum[2] && sum[2] == sum[3]);
    if (csv) {
        const char* rk[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("read_%s,%.1f\n", rk[k], rms[k]);
        const char* wk[3] = { "coutSync", "oss", "buffer" };
        for (int k = 0; k < 3; k++) printf("write_%s,%.1f\n", wk[k], wms[k]);
        printf("same,%d\nchecksum,%lld\n", same ? 1 : 0, sum[0]);
        printf("readTotalCin,%.1f\nreadTotalFast,%.1f\n", rms[0] + wms[0], rms[3] + wms[2]);
        return 0;
    }
    const char* rname[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)", "scanf", "手写快读（fread）" };
    const char* wname[3] = { "cout（同步开着）", "ostringstream（≈ 关同步的 cout）", "自己拼 buffer + 一次 fwrite" };
    auto disp = [](const string& t) { int w = 0; for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; w += (c < 0x80) ? 1 : 2; } return w; };
    auto pad = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    printf("n = %d、m = %d（读 %d 个整数，写 %d 个整数）：\n\n", nn, mm, mm + 2, mm);
    printf("  读：\n");
    for (int k = 0; k < 4; k++) printf("    %s %8.1f 毫秒\n", pad(rname[k], 32).c_str(), rms[k]);
    printf("\n  写：\n");
    for (int k = 0; k < 3; k++) printf("    %s %8.1f 毫秒\n", pad(wname[k], 32).c_str(), wms[k]);
    printf("\n  四趟读出来的校验和%s。\n", same ? "完全一致" : "居然不一致！");
    printf("  ⇒ 「最慢的读 + 最慢的写」= %.1f 毫秒，「最快 + 最快」= %.1f 毫秒。时限是 1 秒。\n",
           rms[0] + wms[0], rms[3] + wms[2]);
    return 0;
}

// 数据生成器（P1271 对拍用）：`./p1271Gen <seed> [level]`
//
//   level 0（默认）随机票
//   level 1        ★ **票全投给同一个人** —— 计数排序里 cnt 只有一格非零
//   level 2        ★ **每人恰好一票**（m = n）—— 另一头的极端
//
// ⚠ 题面：1 <= n <= 999，1 <= m <= 2×10⁶，1 <= a_i <= n。
//   小数据对拍只验「答案对不对」；这道题真正要量的是**规模**，那归 genBig.cpp。

#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(1, 8);
    int m = (level == 2) ? n : ri(1, 20);
    printf("%d %d\n", n, m);
    for (int i = 0; i < m; i++) {
        int v;
        if (level == 1) v = 1;
        else if (level == 2) v = i + 1;
        else v = ri(1, n);
        printf("%d%c", v, i + 1 == m ? '\n' : ' ');
    }
    return 0;
}