[C++知识库]Codeforces Round #823 (Div. 2)(A~C)

A. Planets

卫星射击，简单的模拟题

#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
    int t;cin>>t;
    while(t--){map<int,int>mp;
        int n,c;cin>>n>>c;
        for(int i=0;i<n;i++){cin>>a[i];、mp[a[i]]++;}
        int ans=0;
        for(auto i:mp)
            if(i.second>=c)ans+=c;
            else ans+=i.second;
        cout<<ans<<endl;
    }
    return 0;
}

B. Meeting on the Line

题意：每个人到 x0 的所花时间是 ti +| x0 - xi |，求应该把x0设置在哪里

思路：

二分时间，并且check 时间是否合适。最后得到合适的最短时间，用这个最短时间去找每个人能够移动的最大范围的重叠的地方，那么这个重叠的地方就是答案。同时关于怎么check也是找区间，有过有的区间没有重叠的地方，那么这个时间就是不合适的了。

注意：

记得在输出的时候要输出10位，不然会WA

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
double x[100005],t[100005],n,ans;
bool check(double mid){
    double r=1e18,l=0;
    for(int i=0;i<n;i++){
        if(mid<t[i])return 0;
        double time=mid-t[i];
        r=min(r,x[i]+time);
        l=max(l,x[i]-time);
    }
    ans=r;
    return r>=l;
}
signed main()
{
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>x[i];
        for(int i=0;i<n;i++)cin>>t[i];
        double l=0,r=1e18;//模拟时间
        for(int i=1;i<=100;i++){
            double mid=(l+r)/2;
            if(check(mid)){r=mid;}
            else l=mid;
        }
        check(r);
        cout<<fixed<<setprecision(10)<<ans<<endl;
    }
    return 0;
}

C. Minimum Notation

简单模拟

思路：记录最终输出的答案的0~9的个数，之后从小到大输出

1.把每个数的位置记录下来，从0到9枚举 i 的最后一位

2.之后把从i-1的最后一位到?i?的最后一位中间的数记录

2.1 如果是数字是9，9的个数+1

2.2如果是数字是i，i的个数+1

2.3剩下情况，（该数字+1）的个数+1

之后从小到大输出

代码：

#include<bits/stdc++.h>
using namespace std;
char s[200005],ss[200005];
int main()
{
    int T;cin>>T;
    while(T--){
        cin>>s;
        vector<int>v[10];
        int co[10]={0};
        int n=strlen(s);
        for(int i=0;i<n;i++){
            ss[i]=s[i];
            v[s[i]-'0'].push_back(i);
        }
        int l=0;
        for(int i=0;i<=9;i++){
            int r=v[i].size();
            if(r==0)continue;
            if(v[i][r-1]<l)continue;
            for(int q=l;q<=v[i][r-1];q++){
                if(s[q]==(i+'0'))co[i]++;
                else if(s[q]=='9')co[9]++;
                else co[s[q]-'0'+1]++;
            }
            l=v[i][r-1]+1;
        }
        for(int i=0;i<=9;){
            if(co[i]!=0)cout<<i;co[i]--;if(co[i]<=0)i++;
        }
        cout<<endl;
    }
    return 0;
}