P1650 田忌赛马
  • 板块学术版
  • 楼主Archers_wylr
  • 当前回复5
  • 已保存回复5
  • 发布时间2020/11/12 20:46
  • 上次更新2023/11/5 08:12:33
查看原帖
P1650 田忌赛马
209186
Archers_wylr楼主2020/11/12 20:46

我的贪心策略是每次拿出我有的马中最慢(垃圾)的马进行对比

1.从大到小找能不能干掉齐王的马 如果能找到则直接干他(创造的价值最大)

2.如果没有能干过的,找找有没有能平局的,如果有,则干他(依旧价值最大)

3.如果啥也没用,那这匹马唯一的作用就是替别的马去死,那我就去跟最强的马换了

个人感觉这个贪心思路是正确的,但是代码提交只有20分,求大佬指教

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int a[maxn],b[maxn],n,r,f[maxn],ans;
int main(){
	//freopen("a.in.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	r=n;
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		int k=0,t=-1,k1=0;
		for(int j=n;j>=1;j--){
			if(a[i]>b[j]&&f[j]!=-1){
				if(j==r)r--;
				ans++;
				k=1;
				f[j]=-1;
			//	cout<<ans<<"ko"<<" ";
				break;
			}
			if(k1==0&&a[i]==b[j]){
				k1=1;
				t=j;
			}
		}
		if(k==1)continue;
		else {
			if(t!=-1){
				//cout<<t<<endl;
				f[t]=-1;
			//	cout<<ans<<"gan"<<" ";
				continue;
			}
			else{
				f[r]=-1;
				ans--;
				r--;
			//	cout<<ans<<"song"<<" ";
			}
		}
		
	}
//	cout<<endl;
	cout<<ans*200;
}
2020/11/12 20:46
加载中...