题目链接
163. 生日礼物
翰翰 \(18\) 岁生日的时候,达达给她看了一个神奇的序列 \(A_1, A_2, …, A_N\)。
她被允许从中选择不超过 \(M\) 个连续的部分作为自己的生日礼物。
翰翰想要知道选择元素之和的最大值。
你能帮助她吗?
输入格式
第一行包含两个整数 \(N,M\)。
第二行包含 \(N\) 个整数 \(A_1 \sim A_N\)。
输出格式
输出一个整数,表示答案。
数据范围
\(1 \le N,M \le 10^5\),
\(|A_i| \le 10^4\)
输入样例:
5 2
2 -3 2 -1 2
输出样例:
5
解题思路
反悔贪心
首先预处理:把所有的正数和负数合并,最后一定是 \(正数-负数\) 交替的情况,先把所有的正数放入堆中,如果正数段数不大于要求的段数,则显然全选最优,否则考虑合并或者删除某些已选择的正数,而由于选择负数合并或者删除正数,都要求选择的数的绝对值尽量小,答案才会更大,而且选择的数要求不能相邻,如果选择的数相邻的话,必定是一个正数一个负数的情况,正数表示不选这个正数,负数表示选择这个负数,既然选择负数,选择正数必然更优,即选择的数不能相邻,且选择的所有数最小,即转化为 147. 数据备份 这个问题
- 时间复杂度:\(O(nlogn)\)
代码
// Problem: 生日礼物
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/165/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e5+5;
int n,m,a[N],b[N],cnt,L[N],R[N];
void del(int x)
{
L[R[x]]=L[x],R[L[x]]=R[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int st=1,ed=n;
while(st<=n&&a[st]<=0)st++;
while(ed>=1&&a[ed]<=0)ed--;
int t=a[st];
for(int i=st+1;i<=ed;i++)
if((LL)t*a[i]>=0)t+=a[i];
else
b[++cnt]=t,t=a[i];
b[++cnt]=t;
set<PII> s;
int res=0,p=0;
for(int i=0;i<=cnt+1;i++)
{
L[i]=i-1,R[i]=i+1;
if(b[i]>0)res+=b[i],p++;
if(i>=1&&i<=cnt)
b[i]=abs(b[i]),s.insert({b[i],i});
}
b[0]=b[cnt+1]=2e9;
if(m>=p)cout<<res;
else
{
int k=p-m;
while(k--)
{
auto p=s.begin();
int x=(*p).se;
res-=b[x];
int l=L[x],r=R[x];
s.erase(p);
s.erase({b[l],l}),s.erase({b[r],r});
b[x]=b[l]+b[r]-b[x];
s.insert({b[x],x});
del(l),del(r);
}
cout<<res;
}
return 0;
}
原文地址:http://www.cnblogs.com/zyyun/p/16875509.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性