#823 div2

A：

题目：

现在有 n 个行星，第 i 个行星在第 ai 个轨道上，统一轨道存在多个行星。

现在有两种操作

1. 用代价 1 摧毁任何行星。
2. 用代价 c 摧毁一个轨道上的所有行星。

问你最小的代价摧毁所有行星。

思路：

贪心的思考，

对于一个轨道上的星球，如果数量 > c 那么我们肯定是选择操作2，如果小于 c， 那么操作1

代码

void solved()
{
    cin >> n >> m;
    memset(a, 0, sizeof a);

    int ans = 0;

    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a[x]++;
    }

    for(int i = 1; i <= 100; i++)
    {
        if(a[i] <= m) ans+= a[i];
        else ans += m;
    }

    cout << ans << endl;

}

B：

题目：

存在 n 个人住在一条数轴，他们都要去同一个地方开会，并且每个人会花费 t[i] + |xi - x0| 去到达目标位置， t[i] 为第 i 个人穿衣服的时间，x[i] 为当前人的坐标, x0 为会议的坐标。

现在需要我们找到一个地方，可以使得 n 个人都到达会议的时间最短。

思路：

对于位置来说不具有二段性，对于时间来说具有。我们可以二分出一个时间，然后规划出每个人能够根据当前时间走到的范围，如果说所有人的范围最终聚集在一个点上，那么这个点就是答案。

代码

bool check(double mid)
{
    double l = - 2e18, r = 2e18;

    for(int i = 0; i < n; i++)
    {
        if(b[i] > mid ) return false;
        else
        {
            l = max(l, a[i] + b[i] - mid);
            r = min(r, a[i] + mid - b[i]);
        }
    }

    ans = l;
    return r - l >= 1e-8;
}


void solved()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];

    double l = 0, r = 1e9;

    for(int i = 0; i < 100; i++)
    {
        double mid = (l + r ) / 2;

        if(check(mid)) r = mid;
        else l = mid;
    }

    printf("%0.10f\n", fabs(ans));
}
int

C：

题目：

现在有一个由 0 - 9 组成的字符串，现在可以执行一下任意操作

可以选择第 i 个位置上的的数字 d，然后删除它，在任意位置插入min(d+1,9),

问你最小可以获得的字典序字符串是什么

思路：

字典序首先比较第一个字符，所以对于出现的最小的字符，我们肯定不希望它被操作然后减小。

所以之后因为按照字典序排列其他的按顺序排列即可。

贪心的来说，从前往后来说字典序依次减小，但是不好操作较大值。

所以反过来从后往前字典序依次减小，每次维护最小值，遇到较大值就可以往后放。

因为插入任意顺序，我们假设每次默认插入升序排列。

代码

void solved()
{
    string s;
    cin >> s;
    int len = s.size();

    int minn = 0x3f3f3f3f;
    string ans;


    for(int i = len - 1; i >= 0; i--)
    {
        int x = s[i] - '0';
        minn = min(minn, x);

        if(x > minn) ans += min(9, x +1) + '0';
        else ans += x + '0';


    }

    sort(ans.begin(), ans.end());

    cout << ans << endl;

}