月赛B,WA了sub1,2过了sub345
  • 板块题目总版
  • 楼主NewJeanss
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/10/6 18:37
  • 上次更新2023/11/5 11:47:45
查看原帖
月赛B,WA了sub1,2过了sub345
282080
NewJeanss楼主2020/10/6 18:37
#include <bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,m,c,v,ans,res[N];
struct card{
	int a,b,id;
}a[N],b[N];
inline bool cmp(card a,card b){
	if(a.a==b.a) return a.b>b.b;
	else return a.a<b.a;
}
void solve(int l1,int r1,int l2,int r2){
	int len1=r1-l1+1,len2=r2-l2+1;
	if(len2>=len1) r2=l2+len1-1;//只取D手牌中和C一样数目x的前x大
	else ans-=(len1-len2)*c,l1=r1-len2+1;
	for(int i=l2;i<=r2;i++) ans+=a[i].b;
	for(int i=l2,j=l1,ii=r2,jj=r1;i<=ii&&j<=jj;)
	{
		//cout<<i<<" "<<ii<<" "<<j<<" "<<jj<<endl;
    	if(a[i].b>=b[j].b){
    		res[b[j].id]=a[i].id;
    		ans+=c; i++; j++;
    	} 
    	else{
    		res[b[j].id]=a[ii].id;
       		ans-=c; j++; ii--;
   		}
	}	
}
signed main(){
	int s,j,e;
	ios::sync_with_stdio(false); cin.tie(0);
	while(cin>>n>>m>>c>>v){
		for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b,a[i].id=i;//D
		for(int i=1;i<=m;i++) cin>>b[i].a>>b[i].b,b[i].id=i;//C
		sort(a+1,a+n+1,cmp);
		sort(b+1,b+m+1,cmp);
		ans=v; s=1;//对于D的每张卡 
		memset(res,-1,sizeof(res));
		for(int i=1;i<=m;i++){//对于C的每张卡
			if(b[i].a<a[s].a){
				while(b[i].a<a[s].a&&i<=m) i++,ans-=c;
			}else{
				while(a[s].a<b[i].a&&s<=n) s++;
			}
			if(a[s].a!=b[i].a){
				continue;
			}
			j=i+1;//[i,j] 
			while(b[j].a==b[i].a&&j<=m) j++;
			j--;
			e=s+1;//[s,e]
			while(a[e].a==a[s].a&&e<=n) e++;
			e--;	
			solve(i,j,s,e);
			i=j; s=e+1;//下一次起点 
			if(s>n){
				ans-=(m-j)*c; break;
			}
		}
		cout<<ans<<endl;
		for(int i=1;i<=m;i++){
			cout<<res[i]<<endl;
		}
	}
	return 0;
}
2020/10/6 18:37
加载中...