Codeforces Round #590 (Div. 3)

A - Equalize Prices Again

题意：给n个商品，每个商品价格不同，要调整他们的价格，使得总价不下降且他们的价格相等，在此基础上最小化总价。

题解：找超过原总价的最小的n的倍数。

void test_case() {
    int n;
    scanf("%d", &n);
    ll sum = 0;
    for(int i = 1; i <= n; ++i) {
        ll tmp;
        scanf("%lld", &tmp);
        sum += tmp;
    }
    sum = (sum + n - 1) / n;
    printf("%lld\n", sum);
}

B1 - Social Network (easy version)

见下

B2 - Social Network (hard version)

题意：有个手机，屏幕能显示k个聊天窗口，已知n个人给你发消息的序列，求最终的聊天窗口。

调整规则如下：

1. 假如当前聊天窗口中有这个人，啥都不做，结束
2. 否则，若窗口已满，去掉最底部的窗口
3. 其他窗口下移，新的显示在顶部

题解：看起来就是个队列，然后还要查队列里有没有某个元素，这个用个set就完事了。不过最后题目要从顶部到底部输出，所以一开始就用双端队列就很方便。

set<int> s;
deque<int> q;

void test_case() {
    s.clear();
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        int id;
        scanf("%d", &id);

        if(s.count(id))
            continue;
        else {
            if(q.size() >= k) {
                s.erase(q.front());
                q.pop_front();
            }
            q.push_back(id);
            s.insert(id);
        }
    }
    printf("%d\n", (int)q.size());
    while(q.size()) {
        printf("%d ", q.back());
        q.pop_back();
    }
    printf("\n");
}