[ABC268F] Best Concatenation Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 个由 X 和数字构成的字符串，你需要对其进行排列并拼接成新的字符串 $T$$T$ 以最大化其分数。定义其分数为对于字符串中每一个数字，使数字对应的数值乘上其之前 X 的数量，并求和。输出分数最大值。

Solution

首先一个显然的结论即为对于题目定义的分数，同一字符串内部的 X 对其数字的贡献，与字符串在排列中的顺序无关。

于是我们考虑其它字符串的 X 对字符串数字的贡献，我们考虑字符串 $S_i,S_j$$S_i, S_j$，令 $cn{t}_i$$cnt_i$ 表示字符串 $i$$i$ 中 X 的数目，令 $su{m}_i$$sum_i$ 表示字符串 $i$$i$ 中所有数字数值之和。显然若 $S_i$$S_i$ 在 $S_j$$S_j$ 之前，$j$$j$ 对 $i$$i$ 无贡献，$i$$i$ 对 $j$$j$ 的贡献为 $cn{t}_i\times su{m}_j$$cnt_i \times sum_j$。反之则为 $cn{t}_j\times su{m}_i$$cnt_j \times sum_i$。

则不难想到若我们要将 $S_i$$S_i$ 放在 $S_j$$S_j$ 之前，那么一定有这样的贡献更大一些，即 $cn{t}_i\times su{m}_j>cn{t}_j\times su{m}_i$$cnt_i \times sum_j \gt cnt_j \times sum_i$。

所以我们直接考虑对字符串进行排序，比较规则则按照刚才的式子跑一下即可。

同时我们也可以从意义上感性理解，显然只有前面的 X 对后面的数字产生贡献，所以我们将 X 更多数字更少的放在前面，则 ${\displaystyle \frac{cn{t}_i}{su{m}_i}}$$\dfrac{cnt_i}{sum_i}$ 可以作为一个类似估价函数的作用进行排序，转换一下即我们刚才证明的上式。

同时对于此贪心的证明，考虑若满足偏序关系 $S_1,S_2$$S_1, S_2$ 和 $S_2,S_3$$S_2, S_3$，那么一定也有 $cn{t}_1\times su{m}_3>cn{t}_3\times su{m}_1$$cnt_1 \times sum_3 \gt cnt_3 \times sum_1$，所以也有偏序关系 $S_1,S_3$$S_1, S_3$，也就是 $S_1,S_2,S_3$$S_1, S_2, S_3$，扩展到整个序列依然满足。

存在双倍经验 LG-P1080 [NOIP2012 提高组] 国王游戏。

Code

xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
struct Node{string S; int sum, cnt;}d[210000];
27
ll ans(0);
28

29
int main(){
30
    N = read();
31
    for(int i = 1; i <= N; ++i){
32
        cin >> d[i].S;
33
        for(auto c : d[i].S)
34
            if(c == 'X')++d[i].cnt;
35
            else d[i].sum += c - '0';
36
    }sort(d + 1, d + N + 1, [](const Node &a, const Node &b)->bool{return (ll)a.sum * b.cnt < (ll)b.sum * a.cnt;});
37
    ll cur(0);
38
    for(int i = 1; i <= N; ++i)
39
        for(auto c : d[i].S)
40
            if(c == 'X')++cur;
41
            else ans += cur * (c - '0');
42
    printf("%lld\n", ans);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

UPD

update-2023_01_18 初稿