本文共 1130 字，大约阅读时间需要 3 分钟。

思路大体相同,可惜最后没有特判结尾

$因为负数温度形成一个一个的连通块$

$那么一开始假设最坏,在每个连通块的开始换冬季轮胎$

$在每个连通块的结尾换夏季轮胎$

$接下来发现连通块之间假如不换任何轮胎可以减少2次换轮胎次数$

$但是这样会让冬季轮胎多用几天$

$所以把所有连通块的间隔天数扔进优先队列即可$

但是注意,最后一次可能可以直接用到结尾,特判

#include 
   
    using namespace std;const int maxn=2e5+10;int n,m,a[maxn],top;struct p{	int l,r;}id[maxn];priority_queue
    
     
      ,greater
      
        >q;int main(){	cin >> n >> m;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i<=n;i++)	{		if(a[i]<0)		{			id[++top].l=i;			while(a[i]<0)			{				id[top].r=i;				i++;			}			m-=(id[top].r-id[top].l+1);			i--;		}	}	int ans=top*2;	if(m<0)	{ cout<<-1; return 0; }	for(int i=2;i<=top;i++)		q.push(id[i].l-id[i-1].r-1);	while( !q.empty() )	{		int minn=q.top(); q.pop();		if(m-minn>=0)	m-=minn,ans-=2;		else	break;	}	if(top&&m>=(n-id[top].r))	ans--;	cout<
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107280570 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！