首页 > 编程学习 > 2022/8/18 总结

2022/8/18 总结

发布时间:2022/8/18 19:02:04

A.P2587 [ZJOI2008]泡泡堂

  • 好家伙,久违的贪心所以说挂了

Solution

  • 古人的智慧;

  • 但实际上这道题和田忌赛马有所区别,已知有一种比较优的方法是用己方最鶸的换掉敌方最强的,那么为了得分最大,就有如下策略:

    • 当己方最强比敌方最强强时,得 \(2\) 分;
    • 否则,如果己方最弱比敌方最弱强,得 \(2\) 分;
    • 否则,用己方最弱换掉敌方最强。如果刚好平局,按平局计算;
AC code
#include<bits/stdc++.h>
using namespace std;

inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=s*10+int(ch-'0');
		ch=getchar();
	}
	return s*f;
}

const int N=1e5+10;

int n;
int a[N],b[N];

int count(int x[],int y[]){
	int ans=0;
	int lx=1,ly=1,rx=n,ry=n;
	while(lx<=rx && ly<=ry){
		if(x[lx]>y[ly]){
			ans+=2;
			++lx,++ly;
		}
		else if(x[rx]>y[ry]){
			ans+=2;
			--rx,--ry;
		}
		else{
			ans+=(x[lx]==y[ry]);
			++lx;
			--ry;
		}
	}
	return ans;
}

int main(){
//	freopen("bubble.in","r",stdin);
//	freopen("bubble.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		b[i]=read();
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	printf("%d %d",count(a,b),(n<<1)-count(b,a));
	return 0;
}
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号