CF Round 880(Div. 2) 题解

2023/6/21 C++ 算法竞赛 Div. 2 题解 CodeForce

A-C题解

A. Destroyer

题解

发现只要大的数不比小的数多就行

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int a[N];
int cnt[N];
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        memset(cnt,0,sizeof(cnt));
        int M=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            M=max(M,a[i]);
            cnt[a[i]]++;
        }
        bool flag=false;
        for(int i=0;i<M;i++)
        {
            if(cnt[i+1]>cnt[i])
            {
                flag=true;
                break;
            }
        }
        if(flag)
            cout<<"NO"<<'\n';
        else
            cout<<"YES"<<'\n';
    }
    return 0;
}

B. Astrophysicists

题解

可以发现每个人都尽可能拿多一点(模后余数小于 )是更优的

但是并不是全拿最多是最优的

同时可以发现能赚的总银币数一定能被 整除

这是因为 ,所以

如果每个人都拿尽可能多的银币(指模后余数尽可能接近 )，那么总共能拿 个银币

那么满足条件的赚的最多的银币数为

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ceil(ll n,ll k)
{
    if(n%k==0)
        return n/k;
    return n/k+1;
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll n,k,g;
        cin>>n>>k>>g;
        if(n<=2)
            cout<<0<<'\n';
        else
            cout<<min(k*g,n*(ceil(g,2)-1)/g*g)<<'\n';
    }
    return 0;
}
img_show