贪心

T1 B3928 [GESP202312 四级] 田忌赛马（简单版）

没有思考的贪心，没有平局，且只需要求最大的获胜次数即可，所以可以直接排序，之后使用两个指针

i,j

代表枚举至第几匹马，如果能赢就立刻将

i+1,j+1

如果无法获胜就拿更高级的马继续比，直到没有马了

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,ans(0);
int a[maxn],b[maxn];
int main(){
	cin>>n;
	for(int i(1);i<=n;i++){
		cin>>a[i];
	}
	for(int i(1);i<=n;i++){
		cin>>b[i];
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int i(1),j(1);
	while(i<=n&&j<=n){
		if(b[j]<a[i]){
			i++; //如果可以就立刻赢
			j++;
			ans++;
		}else{
			i++; //拿更高级的马
		}
	}
	cout<<ans<<'\n';
	return 0;
}

T2 P1650 田忌赛马（加强版）

比T1难得多，需要考虑的变成了最大利益，赢一局200钱，输一局-200前，平局不加不扣

面对这种情况，一开始想的和上一题一样，赢的越多不就更优吗？其实只争赢的局数最大无法保证最优，比如赢一局，输两局和平三局明显是不一样的结果，平三局明显更优

所以对于这种情况我们的思路是：

比较最大值
如果田忌最大值小于齐王的，就比较最小值
如果最小值也比不过就去消耗齐王最大值

使用双端队列对思路进行模拟，使其比数组操作起来更简单

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,ans(0);
int a[maxn],b[maxn];
bool cmp(int a,int b){
	return a>b;
}
deque<int>tj,qw;
int main(){
	cin>>n;
	for(int i(1);i<=n;i++){
		cin>>a[i];
	}
	for(int i(1);i<=n;i++){
		cin>>b[i];
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	for(int i(1);i<=n;i++){
		tj.push_back(a[i]);
		qw.push_back(b[i]);
	}
	while(tj.size()&&qw.size()){
		if(tj.front()>qw.front()){
			ans++;
			tj.pop_front();
			qw.pop_front();
		}else if(tj.back()>qw.back()){
			ans++;
			tj.pop_back();
			qw.pop_back();
		}else{
			if(tj.back()<qw.front()){
				ans--;
			}
			tj.pop_back();
			qw.pop_front();
		}
	}
	cout<<ans*200<<'\n';
	return 0;
}

9.26 贪心专题

文章操作

贪心

T1 B3928 [GESP202312 四级] 田忌赛马（简单版）

T2 P1650 田忌赛马（加强版）

相关推荐

评论

9.26 贪心专题