Educational Codeforces Round 2 个人总结A-D

Educational Codeforces Round 3

A. USB Flash Drives

• 降序排序后，贪心，甚至不会爆longlong

void solve()
{
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(all(a));reverse(all(a));
    int s=0,ans=0;
    for(int i=0;i<n;i++)
    {
        if(s>=m)    break;
        s+=a[i],ans++;
    }
    cout<<ans<<endl;
    return;
}

B. The Best Gift

• 大意：有多少种互不相同不同的组合
• 用map记录这个类型出现的次数
• 一本书的贡献为 与这本书不同类型的数量

void solve()
{
    int n,m;
    cin>>n>>m;
    LL ans=0,s=0;
    vector<int> a(n);
    map<int,int> mp;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
        s++;
    }
    for(auto it:mp)
    {
        ans+=(it.se*(s-it.se));
    }
    cout<<ans/2ll<<endl;
 
    return;
}

C. Load Balancing

• 大意:求让最大值和最小值的差最小的操作次数

• \(s\) 为所有数之和，\(k\) 代表平均数，\(r\) 代表余数

• $k = \frac{s}{n} $, $ r =s\%n $

• 当 $ r=0 $ ，最大值和最小值的差为 \(0\)，答案即为\(\sum_{i=1}^n \max(a_i-k,0)\)

• 当 $ r=1 $ ，最大值和最小值的差为 \(1\)，答案即为\(\sum_{i=1}^{n-r} \max(a_i-k,0)+\sum_{i=n-r+1}^{n} \max(a_i-k-1,0)\)

LL a[N],b[N];
void solve()
{
    LL n;
    cin>>n;
    LL ans=0,s=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    sort(a+1,a+1+n);
    LL k=s/n,r=s%n;
    for(int i=1;i<=n;i++)
        b[i]=k;
    for(int i=n;i>=n-r+1;i--)
    {   
        b[i]++;
    }
    for(int i=1;i<=n;i++)
        ans+=max(a[i]-b[i],0ll);
 
    cout<<ans<<endl;
    return;
}