考试

Posted on In

题目大意：共有 𝑛 名学生参加了一次考试，成绩被记为 𝑎𝑖 。老师不希望看到有两人取得相同的成绩，因此会调整分数，并且只会给学生加分。现在你想要知道，最终所有人分数总和最少是多少。

由题发现的性质：n个数，最后的序列一定是n个不同的数字

我们考虑开两个数组，一个来记录原数字，一个来记录应变成的数字

我们顺序的扫，把每个数字都变成自己应该变成的数字

因为1 1 2 3 4 4变成1 5 2 3 4 6

与变成1 2 3 4 5 6其实是一样的

考试的时候我担心1e9的map会出问题，很傻逼的还花了半个小时，把数字转成了字符串

其实不应该在T1花太多时间的

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e5 + 66;

int n;
int a[N], b[N];
map<string, bool>mp;

signed main()
{
    int i, n = read();
    for (i = 1; i <= n; ++ i) a[i] = read();

    sort(a + 1, a + n + 1);
    for (i = 1; i <= n; ++ i) b[i] = a[i];

    for (i = 2; i <= n; ++ i)
    {
        char C[66]; int NUM = 0;
		char now[66]; int p = 0;

        int tibu = a[i];
        memset(C, 0, sizeof C), NUM = 0;
        while (tibu)
        {
            C[++ NUM] = tibu % 10 + 48;
            tibu /= 10;
        }
        memset(now, 0, sizeof now), p = 0;
        for (int len = NUM; len >= 1; -- len) now[++ p] = C[len];

        string s = (now+1); 

        if (a[i] == a[i - 1] || mp[s] == 1)
        {
            b[i] = b[i - 1] + 1;

            tibu = b[i];
            memset(C, 0, sizeof C), NUM = 0;
            while (tibu)
            {
                C[++ NUM] = tibu % 10 + 48;
                tibu /= 10;
            }
            memset(now, 0, sizeof now), p = 0;
            for (int len = NUM; len >= 1; -- len) now[++ p] = C[len];

            string st = (now+1);
            mp[st] = 1;
        }
    }
    int res(0);
    for (i = 1; i <= n; ++ i) res += b[i];

    put(res);
    return 0;
}