HJ174 交换到最大

题目题解(26)讨论(9)排行简单 通过率41.93% 时间限制3秒 空间限制256M知识点贪心校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定一个仅由数字 0-90-9 构成的字符串 ss。一次操作可按如下方式进行∙ ∙ 从 ss 中选择既不是最左端字符也不为 00的某一字符∙ ∙ 将该字符的数值减少 11∙ ∙ 随后把它与左侧相邻字符交换位置。例如字符串 10231023 经过一次操作可以变成 11031103 或 10221022。你可以不限次数地执行上述操作。请计算能够得到的字典序最大的字符串并输出该字符串。输入描述第一行输入一个整数 t(1≦t≦104)t(1≦t≦104)表示测试用例数量。此后 tt 行每行输入一个不含前导零的数字字符串 ss满足 1≦∣s∣≦2×1051≦∣s∣≦2×105。保证所有测试用例的 ∣s∣∣s∣ 之和不超过 2×1052×105。输出描述对于每个测试用例在一行上输出通过任意次数操作后能够得到的字典序最大的字符串。示例1输入6 19 1709 11555 51476 9876543210 5891917899复制输出81 6710 33311 55431 9876543210 7875567711复制说明以 1919 为例 ∙ ∙ 1919 →→ 8989 ∙ ∙ 8989 →→ 8181得到答案 8181。 再以 17091709 为例可按如下序列操作 ∙ ∙ 17091709 →→ 17801780 ∙ ∙ 17801780 →→ 61806180 ∙ ∙ 61806180 →→ 67106710最终得到答案 67106710。#include iostream #include string #include vector #include algorithm using namespace std; void solve() { string s; cin s; int n s.length(); for (int i 0; i n; i) { int best_val s[i] - 0; int best_pos i; // 在窗口内寻找能产生最大价值的来源 for (int j i; j min(i 10, n); j) { int current_val (s[j] - 0) - (j - i); if (current_val best_val) { best_val current_val; best_pos j; } } // 物理移动来源字符到当前位置i while (best_pos i) { swap(s[best_pos], s[best_pos - 1]); best_pos--; } // 将当前位置i的字符值更新为计算出的最优值 s[i] (char)(best_val 0); } cout s endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin t; while (t--) { solve(); } return 0; }