Educational Codeforces Round 3 个人总结A-D

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;

}

D. Gadgets for dollars and pounds

二分，前缀和，贪心
大意：在 $n$ 天中买东西，每天有不同的汇率，$m$ 个商品，只能使用pounds或dollars，要买 $k$ 个，但只有 $s$ 元钱，判断能不能买，能输出哪天能买完，和哪一天买第几个商品
在 $1,...,n$ 天中，若第 $x$ 天能买完 $k$ 个，那第 $k+1$ 天也能买完，也就是在 $1,...,n$ 天中找到最小满足条件的 $x$，且第 $x-1$ 天不能买完，这是有单调性的，所以我们二分哪天能买完
check中，在 $1,...,x$ 天中找到最小pounds和dollars的汇率分别是$a1$ 和 $b1$，设消费为 $sum$ 。题目并没有限制每天购买商品的数量，我们等到汇率最小那天买完是最划算的贪心
这里就有一个问题，如何去确定换了前去买用pounds，还是用dollars的？
因为买$k$ $(1 ≤ k ≤ 2·10^5)$ 个商品，可以对pounds，和dollars进行排序，用前缀和处理
$sum=s1[x]·a1+s2[y]·b1$ $(0 ≤ x ≤ \text{pounds商品个数},0 ≤ y ≤ \text{dollars商品个数},x+y=k)$,运用前缀和就可以在$O(k)$的时间内处理出第 $x$ 天结束的最小花销
剩下的输出方案,记录下最小花销下的 $x$ 、 $y$ 和 pounds和dollars 汇率最小的日子就很容易解决了

代码有点丑QAQ

const int N = 200010;

LL n,m,k,s,a[N],b[N];

int id,d1,d2;

LL cnt1=0,cnt2=0,s1[N],s2[N];

PII c1[N],c2[N];

bool check(LL x)

{

    LL a1=1e18,b1=1e18;

    for(int i=1;i<=x;i++)

    {

        if(a[i]<a1)

            d1=i,a1=a[i];

        if(b[i]<b1)

            d2=i,b1=b[i];

    }

    LL sum=1e18;

    for(int i=0;i<=k;i++)

    {

        if( !(i<=cnt1&&k-i<=cnt2))    continue;

        LL t1=s1[i],t2=s2[k-i];

        LL r1=t1*a1,r2=t2*b1;

        if(r1+r2<sum)

            sum=r1+r2,id=i;

    }

    if(sum<=s)    return true;

    else return false;

}

void solve()

{

    cin>>n>>m>>k>>s;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<=n;i++)

        cin>>b[i];

    for(int i=1;i<=m;i++)

    {

        LL t,cc; cin>>t>>cc;

        if(t==1)    c1[++cnt1].fi=cc,c1[cnt1].se=i;

        else

            c2[++cnt2].fi=cc,c2[cnt2].se=i;

    }

    sort(c1+1,c1+1+cnt1);

    sort(c2+1,c2+1+cnt2);

    for(int i=1;i<=cnt1;i++)

        s1[i]=s1[i-1]+c1[i].fi;

    for(int i=1;i<=cnt2;i++)

        s2[i]=s2[i-1]+c2[i].fi;

    if(check(n)==false)

    {

        cout<<-1<<endl;    return;

    }

    int l=1,r=n;

    while(l<r)

    {

        int mid=(l+r)>>1;

        if(check(mid))  r=mid;

        else l=mid+1;

    }

    if(check(l))

    {

        cout<<l<<endl;

        vector<PII> ans;

        int j=0;

        for(int i=1;i<=id;i++)

            ans.pb({d1,c1[++j].se});

        j=0;

        for(int i=id+1;i<=k;i++)

            ans.pb({d2,c2[++j].se});

        for(auto &it:ans)

            cout<<it.se<<" "<<it.fi<<endl;

    }

    return;

}

巴特西

Educational Codeforces Round 3 个人总结A-D

最新文章

热门文章