In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.
题意: 输入 n k l 你要做 n 个桶, 每个桶需要 k 个木板, 用木板拼好的桶相互之间体积的差距<=l, 桶的体积大小就是最短的那根木板的长度大小.
第二行 共 n*k 个数, 分别表示 n*k 个木板的长度.
分析:
先对边排个序
不存在的情况, 就是 a[n]-a[1]>l, 那就是不存在, 因为要是差距尽可能小, 前 n 小的都分别作为 n 个桶的一块木板, 那么这之中最大的差距就是 a[n]-a[1], 要是 a[n]-a[1]都满足条件 (<=l) 了, 那就满足条件了.
其次, 要使体积和最大输出体积和, 我毛想想觉得 s=a[1]+......a[n], 结果 WA 了, 引起了我的深思.
因为:
- eg:4 3 17
- 1 2 3 5 9 13 18 21 22 23 25 26
它可以这样组 3 组:
- 18 25 26
- 13 22 23
- 1 2 3
- 5 9 21
这样体积为 1+5+13+18=37, 不是简单地
1 +2 +3 +5=11
所以我的思路: 先要找到最大的满足条件的数, 可以用二分找更快, 在这组样例中, 是 18, 它 - a[1]<=l,
那么从最后开始去 k-1 个和 18 拼, s+=18, 再下一个数 13(
25 26)
, 再从最后找 k-1 个数(
22 23
),
再下一个数 9, 发现再 k-1 个数不够了, 那就从头开始找了,(1 2 3)一组, 在去 (5 9 13) 时, 发现 13
已经被取走, 那就 s+=5 就可以了.
- #include <iostream>
- #include<cstring>
- #include<string>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<deque>
- #include<vector>
- #define ll long long
- #define inf 0x3f3f3f3f
- #define mod 1000000007;
- using namespace std;
- ll a[100005];
- bool cmp(ll a,ll b)
- {
- return a<b;
- }
- int main()
- {
- ll n,k,l;
- scanf("%I64d%I64d%I64d",&n,&k,&l);
- for(ll i=1;i<=n*k;i++)
- {
- scanf("%I64d",&a[i]);
- }
- sort(a+1,a+1+n*k,cmp);
- if(a[n]-a[1]>l)
- {
- printf("0");
- }
- else
- {
- ll s=0;
- ll p=-1;
- for(ll i=n*k;i>=1;i--)
- {
- if(a[i]-a[1]<=l)
- {
- p=i;// 找到标准数, 最大的满足条件的数
- break;
- }
- }
- s=0;
- int num=0;// 记录从标准数向前取了多少
- int j=p;
- for(ll i=n*k;i-(k-1)>p;i=i-(k-1))// 先从后往前取
- {
- s+=a[j--];
- num++;
- }
- for(ll i=1;i<p-num+1;i=i+k)// 在从前往后取
- {
- s+=a[i];
- }
- printf("%I64d",s);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2614816.html