今天下午比赛T3求调(反悔贪心)
  • 板块学术版
  • 楼主mortis_life
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/10/14 20:06
  • 上次更新2023/11/2 13:48:43
查看原帖
今天下午比赛T3求调(反悔贪心)
751442
mortis_life楼主2023/10/14 20:06

考场上想的是错解,但是我感觉以下代码没问题

#include<bits/stdc++.h>
using namespace std;

inline long long read()
{
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0' && ch<='9') x=(long long)x*10+ch-'0',ch=getchar();
    return x*f;
}

int T;
int n;long long c[200200],sum,x111,b[2000],tot,m1;bool vis[100];


signed main()
{
	cin>>T;
	while(T--)
	{
		priority_queue<long long> q;
		cin>>n;sum=0;
		for(int i=1,x;i<=n;i++) x111=read();
		for(int i=1;i<=n;i++) c[i]=read();
		q.push(-c[1]);bool flg=0;
		for(int i=2;i<=n;i++)
		{
			tot=0;m1=0;flg=0;
			while(!q.empty()&&q.top()>=0) m1+=q.top(),q.pop(),flg=1;
			if(c[i]+q.top()>=0||(flg&&c[i]+m1>=0)) {
				if(flg) sum+=c[i]+m1,q.push(0);
				else sum+=c[i]+q.top(),q.pop(),q.push(0);
				q.push(-2*c[i]);
			} 
			else if(flg) q.push(m1),q.push(-c[i]);
			else q.push(-c[i]);
		}
		cout<<sum<<endl;
	}
	return 0;
}
2023/10/14 20:06
加载中...