E赛马简单题解(vector+upper bound)
赛马
https://ac.nowcoder.com/acm/contest/5758/E
链接:https://ac.nowcoder.com/acm/contest/5758/E
来源:牛客网
题目描述
一天小明与他同学准备赛马,他们每人有n匹马,每匹马有一个固定的战力值,战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序,小明在更改自己马出场顺序后最多能赢多少场比赛。
输入描述:
输入t,代表有t组数据。每组数据输入正整数n,每人的马匹数量。下一行输入n个值a[i],代表小明每匹马的战力值。接下来一行输入n个值b[i],代表对手按顺序出场的每匹马的战力值。(t<=10, n<1000,1<=i<=n,a[i]<1e6,b[i]<1e6)
输出描述:
小明在更改马匹出场顺序后,最多能赢的场数。
分析:这道题的思路不难想,是很简单基础的思想,类似于田忌赛马,用手中比对方快一点的马去进行比赛,可以说是一种另类的贪心思想。。。
这道题的难点在于如何实现,如果选错了方法代码将十分繁琐
要解决的有两个困难的地方
1.已经上过场的马如何去除
2.如何快速寻找战力最相近的马
第一个问题采取vector解决,使用erase这个函数快速删除已经上场的马
第二个问题使用upper bound解决,快速找到比对手马战力高且差值最小的马
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include <map> #include <queue> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { vector<int>v; int i,j,n,t,ans,temp; int a[1005],b[1005]; cin>>t; while(t--) { cin>>n; ans=0; v.clear(); for(i=0;i<n;i++) { cin>>a[i]; } for(i=0;i<n;i++) { cin>>b[i]; } sort(a,a+n); for(i=0;i<n;i++) { v.push_back(a[i]); } //vector<int>::iterator it; temp=n; for(i=0;i<n;i++) { int t=upper_bound(v.begin(),v.end(),b[i])-v.begin(); if(t<temp) { ans++; temp--; v.erase(v.begin()+t); } } cout<<ans<<endl; } return 0; }