CodeForces985C-Liebig's Barrels

描述

题解

二分加贪心。先确保前 ii 桶可以分配为相邻的 kk 个，并且保证 a[i∗k+j]−a[1]<=la[i∗k+j]−a[1]<=l，这样就能保证所有的差不大于 ll，如果不能保证这个条件，说明此时已经无法分配相邻的 kk 个了，而需要将剩下的没有组装的桶先分配一个满足条件的最大的，然后剩下的再分给这些没有组装完成的桶（当然这部分不用代码写出来）。

代码

AC：

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

const int MAXN = 1e5 + 10;

int n, k, l;

int a[MAXN];

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);

    cin >> n >> k >> l;

    int tmp = n * k;

    for (int i=1;i<=tmp;i++) cin>>a[i];

    sort(a+1,a+tmp+1);

    if (a[n]-a[1]>l) cout<<"0"<<endl;

    else

    {

        long long ans=0;

        for (int i=1,j=n-1;i<=n;i++,j--)

        {

            if (a[i*k+j]-a[1]<=l) ans+=a[(i-1)*k+1];

            else

            {

                int p=upper_bound(a+(i-1)*k+1,a+tmp+1,a[1]+l)-a-1;

                ans+=a[(i-1)*k+1];

                while(j--) ans+=a[p--];

                break;

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

CodeForces985C-Liebig's Barrels

描述

题解

代码

最新文章

热门文章