P1650 田忌赛马

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

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

2.如果没有能干过的，找找有没有能平局的，如果有，则干他（依旧价值最大）

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

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

CPP

#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;
}

讨论操作

回复

相关推荐

P1650 田忌赛马