A. Boboniu Chats with Du
题意
给出一个数组,已知数组长度n, m,d
从左至右依次取数,若数大于m则之后连续的d个数不能拿
要求获得一个排列使得最后取到的数最大
题解
考虑贪心取数 我们需要尽量多的取出更大的数
首先将数组中的数依据>m分成两组
我们需要让取出的数的总和最大那么两组按照降序排列
假设有la个大于m的数记A ，lc个小于等于m的数记为B
贪心的策略是:
ABB..(d个B)..BBABB…BB ..(多出的B)A
因为最后一个位置取了之后不会因为连续d个数不能拿导致损失
所以安排最后一个为A,还能在前面多拿几个B
观察发现假如拿x个A那么会消耗(x-1)×(1+d)+1个数其中x数被记入答案
而其他的数将不被计入答案，这些数可以是A也可以是B
那么让余下的n-(x-1)×(1+d)-1个数从B中挑选最大的几个
所以枚举拿多少个A 更新答案 需要求出两组数降序排列的前缀和
(只能从B中选因为它们不会产生损失使之后d个数不能拿)
若B的总数无法提供n-(x-1)×(1+d)-1个数
那么相当于拿走一个A后面连续的d个数都是A
唯一可能的合法的策略是AA…AABB….BBB (AA…AAA) 后面可能没有A
确保能取走所有的B以及x个A其他A则需要被舍弃
它不符合ABB..ABBB..ABBB..BBA的策略
而用n-(x-1)×(1+d)-1公式得到所需的B会超过B的总数与实际情况不符
所以为了将这个情况纳入枚举中 我们将B的前缀和延展至长度n
当n-(x-1)×(1+d)-1 >lc 我们不选择直接跳过而是计算取出x个最大的A和所有B的和更新答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double PI=acos(-1);
ll data[Max];
ll pera[Max],perc[Max];
int main() {
Turnoff;
ll n,d,m;
vector<ll>anger,clame;
cin>>n>>d>>m;
for(int i=0;i<n;i++){
ll temp;cin>>temp;
if(temp>m)anger.push_back(temp);
else clame.push_back(temp);
}
sort(anger.begin(),anger.end(),greater<int>());
sort(clame.begin(),clame.end(),greater<int>());
ll ans=0;
for(int i=1;i<=anger.size();i++)pera[i]=pera[i-1]+anger[i-1];
for(int i=1;i<=clame.size();i++)perc[i]=perc[i-1]+clame[i-1];
for(int i=clame.size()+1;i<=n;i++)perc[i]=perc[i-1];
if(anger.empty())for(auto i:clame)ans+=i;
else{
for(ll x=1;x<=anger.size();x++){
ll rest=n-(x-1)*(d+1)-1;
if(rest<0)break;
ll temp=pera[x];
temp+=perc[rest];
ans=max(ans,temp);
}
}
cout<<ans<<endl;
}
|