B3928 tj

· · 题解

这道题嘛......

知道田忌赛马小故事的就知道，这个故事的核心思路就是拿自己最慢的马去对战别人最快的马。我把这种马在下文称作“炮灰”。

我们先来看样例给出的：

如果多一点马？

我的思路：给两个序列从小到大排序，如果我们当前马还没有别人当前最慢的马快，那就去当炮灰。否则就去当前最慢的马那里和它对战。

但是由于炮灰这个操作并不会造成什么影响，只需要跳过当前马就行了。所以可以不用执行。我们只需要执行当这个马大于田忌当前最慢的马的时候去和它对战就行了。

总结：

  1. 对我们和田忌的马的速度进行从小到大排序。
  2. 用两个指针 i，j 分别代表我们的马和田忌当前最慢的马的下标。
  3. 如果我们的第 i 个马的速度大于等于田忌第 j 个马（当前最慢的马）的速度，那么就让 j+1，ans+1。
  4. 输出 ans，代码结束。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+1;
int n,a[N],b[N],ans;
signed main(){
    ios::sync_with_stdio(0);
    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+1+n);
    sort(b+1,b+1+n);
    for(int i=1,j=1;i<=n;i++){
        if(a[i]>=b[j]){
            ++j,++ans;
        }
    }
    cout<<ans;
    return 0;
}