[ABC268F] Best Concatenation Solution
目录更好的阅读体验戳此进入
题面
给定 $ n $ 个由 X
和数字构成的字符串,你需要对其进行排列并拼接成新的字符串 $ T $ 以最大化其分数。定义其分数为对于字符串中每一个数字,使数字对应的数值乘上其之前 X
的数量,并求和。输出分数最大值。
Solution
首先一个显然的结论即为对于题目定义的分数,同一字符串内部的 X
对其数字的贡献,与字符串在排列中的顺序无关。
于是我们考虑其它字符串的 X
对字符串数字的贡献,我们考虑字符串 $ S_i, S_j $,令 $ cnt_i $ 表示字符串 $ i $ 中 X
的数目,令 $ sum_i $ 表示字符串 $ i $ 中所有数字数值之和。显然若 $ S_i $ 在 $ S_j $ 之前,$ j $ 对 $ i $ 无贡献,$ i $ 对 $ j $ 的贡献为 $ cnt_i \times sum_j $。反之则为 $ cnt_j \times sum_i $。
则不难想到若我们要将 $ S_i $ 放在 $ S_j $ 之前,那么一定有这样的贡献更大一些,即 $ cnt_i \times sum_j \gt cnt_j \times sum_i $。
所以我们直接考虑对字符串进行排序,比较规则则按照刚才的式子跑一下即可。
同时我们也可以从意义上感性理解,显然只有前面的 X
对后面的数字产生贡献,所以我们将 X
更多数字更少的放在前面,则 $ \dfrac{cnt_i}{sum_i} $ 可以作为一个类似估价函数的作用进行排序,转换一下即我们刚才证明的上式。
同时对于此贪心的证明,考虑若满足偏序关系 $ S_1, S_2 $ 和 $ S_2, S_3 $,那么一定也有 $ cnt_1 \times sum_3 \gt cnt_3 \times sum_1 $,所以也有偏序关系 $ S_1, S_3 $,也就是 $ S_1, S_2, S_3 $,扩展到整个序列依然满足。
存在双倍经验 LG-P1080 [NOIP2012 提高组] 国王游戏。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
int N;
struct Node{string S; int sum, cnt;}d[210000];
ll ans(0);
int main(){
N = read();
for(int i = 1; i <= N; ++i){
cin >> d[i].S;
for(auto c : d[i].S)
if(c == 'X')++d[i].cnt;
else d[i].sum += c - '0';
}sort(d + 1, d + N + 1, [](const Node &a, const Node &b)->bool{return (ll)a.sum * b.cnt < (ll)b.sum * a.cnt;});
ll cur(0);
for(int i = 1; i <= N; ++i)
for(auto c : d[i].S)
if(c == 'X')++cur;
else ans += cur * (c - '0');
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_18 初稿
标签:cnt,int,题解,sum,Concatenation,times,ABC268F,字符串,define From: https://www.cnblogs.com/tsawke/p/17124346.html