选取k个不相邻的连续线段使和最小(保证元素大于等于0), 可以用双向链表加小根堆处理
现将所有元素插入小根堆中
取出堆顶
ans+=堆顶,删除堆顶,插入堆顶元素加上左右两个元素,删除左右两个元素
本题可转化为类似的问题
将连续的正数和负数合并,因为连续的正数和负数一定一起选,0直接删去
先将所有正数都选上,和记为res
如果正数段数小于M直接输出
否则需要减少的段数记为k
要想减少段数有两种方式:
1.删除一段正数
2.将多段正数和连接他们的负数一起选上
第一种选法直接将res-=这个值
第二种则相当于减去其中负数段的绝对值(画图考虑);
进而将连续的负数记为绝对值
由此就转化为了上面的问题。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
int n,m,l[N],a[N],r[N];
bool st[N];
priority_queue<PII,vector<PII>,greater<PII> > heap;
void remove(int x)
{
l[r[x]]=l[x];
r[l[x]]=r[x];
st[x]=1;
}
int main()
{
cin>>n>>m;
int k=0;
for(int i=1;i<=n;i++)
{
int xi;
scanf("%d",&xi);
if(!xi)continue;
if(!k ||(long long) a[k] * xi < 0 )a[++k]+=xi;
else a[k]+=xi;
}
int res=0,cnt=0;
for(int i=1;i<=k;i++)
{
l[i]=i-1;
r[i]=i+1;
heap.push( {abs(a[i]), i });
if(a[i]>0)res+=a[i],cnt++;
}
while( cnt>m )
{
PII u=heap.top() ;
heap.pop() ;
if(st[u.second])continue;
if(a[u.second]>0 || (l[u.second]!=0 && r[u.second]!=k+1) )
{
res-=u.first;
a[u.second]+=a[ l[u.second] ] + a[ r[u.second] ];
heap.push( { abs(a[u.second]) , u.second } );
remove(r[u.second]);
remove(l[u.second]);
cnt--;
}
}
cout<<res;
}
%%%
交lgWA了
大佬,我这样写,为什么wa了啊
同问 我这里也wa了qwq
应该是0的问题
就是左边界和右边界
是的,我这样过了
%%%
%%%%%%%%%%%%%%%%%%%%%%
%%%
%%%
OrzOrzOrz
巧妙的转换