[CodeForces] AIM Tech Round (Div. 2)

虽然已经弃坑 ACM 了，但是出于某些原因，最近有复习算法和A题的必要……

显然因为好久没干这种事儿了，我的打算是先找以前的 CodeForces Div2 的 ABC 题练练手，然后再开始看书，针对性练习。

这次的题目链接：AIM Tech Round (Div. 2)

---

第一题

可以说前两题等于水题是 CodeForces 的出题套路了，第一题的题意很简单，Luke Skywalker 被困在一个两面墙壁像中间逼近的房间里，题目给出了房间距离和墙的移动速度，以及 Luke Skywalker 自身的宽度，要求你求出他还有多少时间的生命（

随手糊一段代码咯：

#include 

using namespace std;

int main() {
    double a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (b - a) / (c + d);
    return 0;
}

结果……他挂了……

Input
1 9 1 2

Output
2.66667

Answer
2.66666666666666650000

Checker Log
wrong answer 1st numbers differ - expected: '2.6666667', found: '2.6666700', error = '0.0000013'

嗯……很愉快的进度误差……那就改一下咯：

#include 

using namespace std;

int main() {
    double a, b, c, d;
    cin >> a >> b >> c >> d;
    printf("%.18f", (b - a) / (c + d));
    return 0;
}

这份代码很愉快的过了点，耗时 15ms，内存占用 2200KB，中规中矩。

---

第二题

题目比较短，要求你用字母表的前 n 个字母，生成一个字符串，要求每个字母出现的次数完全不一样，同时再给定一个序列，对应位置的字母出现的次数不得超过序列中对应位置的值，最后要求能生成的最长的字符串长度。比如这组输入数据：

3
2 5 5

就是使用 a, b, c 这三个字母生成一个字符串，a 出现次数不能超过 2 次, b 和 c 各自出现的次数不能超过 5 次，他的结果就是 11。
最直接的想法就是，每个出现的都要尽可能多，同时也要不重复，那么上面这个例子的最优解显然为 a 出现 2 次，b、c 中一个为 5 次，另一个为 4 次，将出现的次数加起来就得到了样例输出的结果： 11。
想法有了就是编码了，这题用 STL 中提供的 set 就能很容易的解决：

#include 

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    set iset;
    for (int i = 0; i != n; ++i) {
        int temp;
        cin >> temp;
        while (iset.find(temp) != iset.end())
            temp--;
        if (!temp) continue;
        iset.insert(temp);
    }
    int res = 0;
    for (auto it = iset.begin(); it != iset.end(); ++it) {
        res += *it;
    }
    cout << res << endl;
    return 0;
}

嗯，然后又挂了……

Input
26
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Output
230195899

Answer
25999999675

Checker Log
wrong answer 1st numbers differ - expected: '25999999675', found: '230195899'

欸两次砸在了精度(?)。所以咯，把数据类型改用 uint64_t 估计就没问题了：

#include 

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    set iset;
    for (int i = 0; i != n; ++i) {
        int temp;
        cin >> temp;
        while (iset.find(temp) != iset.end())
            temp--;
        if (!temp) continue;
        iset.insert(temp);
    }
    uint64_t res = 0;
    for (auto it = iset.begin(); it != iset.end(); ++it) {
        res += *it;
    }
    cout << res << endl;
    return 0;
}

Accepted, 内存消耗和时间占用同第一题。

---

第三题

去拿快递了……然后上课……回来再做（