Codeforces Round #823 (Div. 2)

B. Meeting on the Line

题意：有n个人，第i个人的坐标是x_i，从x_i移动到y_i要花 |x_i - y_i| 的时间。除此之外，他还需要 t_i 的时间打扮。试求一点使得所有人到这里所花时间的最大值最小，这个点的坐标可以是小数。

解：如果没有 t_i ，那么就是很简单的取中点；考虑消除 t_i 的影响，把 t_i 看作这个人需要多走的路，那么就有把这个人往左挪 t_i 格或者往右挪 t_i 格两种选项，如果最终答案在这个人左边，那就相当于把他往右挪，反之亦然。可以观察到最终答案只和挪完后最左最右两个人有关，因此我们只关心两种选择可能造成的最大最小值，求其平均值即可。

C. Minimum Notation

题意：给出一个由0-9组成的字符串，每次可以选择任意一个数字，将其+1后放到任意的地方（如果是9的话+1还是9）。执行任意次操作，求字典序最小的结果。

解：感觉比B简单。观察一下样例发现把最小的留在前面，如果后面有比它小的就操作一下放在合适的位置，至于哪里合适不用管，反正最后sort一下就好。脑补一下可以证明是正解，遂交之，T了。仔细观察代码发现自己很弱智地一个字符一个字符输出，遂改之，AC。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll log long
#define maxx 200005
#define inf 1000000009;
int cnt[25]={0};
signed main(){
    int T;
    cin>>T;
    while(T--){
        string s,s0;
        cin>>s;
        int n=s.length();
        for(int i=0;i<=9;i++)
            cnt[i]=0;
        for(int i=0;i<n;i++){
            cnt[s[i]-'0']++;
        }
        for(int i=0;i<n;i++){
            int flag=0,now=s[i]-'0';
            for(int j=now-1;j>=0;j--){
                if(cnt[j]) {
                    flag = 1;
                    break;
                }
            }
            if(flag)
                s0+=(min(now+1,9)+'0');
            else s0+=(now+'0');
            cnt[now]--;
        }
        sort(s0.begin(), s0.end());
        cout<<s0<<'\n';
    }
    return 0;
}