AcWing 电影

重点在于,只选择一部电影.

对于每一部电影,都可以计算出很开心的人数和比较开心的人数,凭此选择最优的电影即可.

如何统计一部电影的很开心&比较开心人数?这题的数据范围很显然不允许对科学家进行线性检索来统计.

一种正确的想法是,统计出每一种语言的使用人数,在这个基础上对于每一步电影,其对应开心人数可以用一个表达式直接表示出来.

如何统计出每一种语言的使用人数?不能用桶,因为10⁹会爆.

(分割线之间可以忽略)

---

这时想到了自己以前写过的一种实现:

struct S{
    int num, ct;
}fac[10000];

我用这个结构体数组记录一个数字的约数及该约数出现在该数字中所具有的指数.

进行统计时,每当我发现了该数字的约数a及其指数b,那么:

fac[idx].num = a;
fac[idx++].ct = ...;

idx初值为0,当统计结束,其值即为fac的size.

实际上,这就类似于离散化操作了.

---

使用离散化方法,就可以存储这些语言及其对应的人数.后者可以使用map映射,而我的实现里则使用了一种笨拙的方法.

离散化函数的实现简单易懂.query是与之配套的检索函数.后者返回的是数组下标.

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

int n, m, a[200010], b[200010], c[200010], sct;
long long big = -1;
int ans;
int s[600010], ct[600010];

void discrete() {
    sort(s, s + 2 * m + n);
    sct = unique(s, s + 2 * m + n) - s;
}

int query(int x) { return lower_bound(s, s + sct, x) - s; }

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[sct++] = a[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        s[sct++] = b[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> c[i];
        s[sct++] = c[i];
    }
    discrete();
    for(int i = 0; i < n; i++) ct[query(a[i])]++;
    for(int i = 0; i < m; i++){
        if((long long)(ct[query(b[i])] * 1000000 + ct[query(c[i])]) > big){
            ans = i;
            big = (long long)(ct[query(b[i])] * 1000000 + ct[query(c[i])]);
        }
        // big = max(big, );
    }
    cout << ans + 1 << endl;

    return 0;
}

// 只选取一个电影

其中,

if((long long)(ct[query(b[i])] * 1000000 + ct[query(c[i])]) > big)

起到了进行具有优先级的比较的作用.