HELP!回报关注
查看原帖
HELP!回报关注
516441
gentleman1楼主2022/11/24 13:56

HELP!一直返回Unknown Error,回报关注

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define int long long
struct edge{
	int val,l,r;
}p[100010];
struct node{
	int val,id;
	bool operator<(node it)const{
		return val>it.val;
	}
};
int n,m,a[100010],ans=0,vis[100010],t;
void del(int x){
	p[x].l=p[p[x].l].l;
	p[x].r=p[p[x].r].r;
	p[p[x].l].r=x;
	p[p[x].r].l=x;
}
priority_queue<node,vector<node> >q;
signed main(){
	/*freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);*/
	cin>>t;
	while(t--){
		cin>>n>>m;ans=0;
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		for(int i=2;i<=n;i++){
			p[i].val=a[i]-a[i-1];
			p[i].l=i-1;p[i].r=i+1;
			q.push((node){p[i].val,i});
		}
		p[1].val=p[n+1].val=0x3f3f3f3f;
		//for(int i=2;i<=n;i++)cout<<p[i].val<<" ";
		//cout<<endl;
		for(int i=1;i<=m;i++){
			while(vis[q.top().id])q.pop();
			node now=q.top();
			//cout<<now.id<<" "<<now.val<<endl;
			q.pop();
			ans+=now.val;
			vis[p[now.id].l]=vis[p[now.id].r]=1;
			p[now.id].val=p[p[now.id].l].val+p[p[now.id].r].val-p[now.id].val;
			q.push((node){p[now.id].val,now.id});
			del(now.id);
		}/**/
		printf("%lld\n",ans);
	}
	return 0;
}
2022/11/24 13:56
加载中...