CF777B Game of Credit Car 题解

· · 题解

CF777B 题解

本题题意：有两个人 S 和 M ，他们每人有一段长度为N的数字，两个人在每一轮游戏中都可以按顺序拿出一个数字，谁的数字小谁就接受一次惩罚。若相等两者 都没有惩罚。

注：M 可以重新排自己的顺序。

问题: M 的最少被惩罚次数 和 S 的最多被惩罚次数 是多少。

本题思路————排序和模拟

  1. 本题只说了可以给 M 排序，但你只要个 M 排了序，那 S 也得要排序，故，两个都要排

  2. 模拟田忌赛马的过程，打不过的，往后推，找下一个比他大的

  3. 重复两遍过程即可输出

接下来————上代码

code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+5;//内存容量
char n[MAXN],m[MAXN];
int l;
int main(){
    cin>>l;
    for(int k=1;k<=l;k++){
        cin>>n[k];//输出字符
    }
    for(int k=1;k<=l;k++){
        cin>>m[k];
    }
    sort(n+1,n+1+l);//排序
    sort(m+1,m+1+l);
    int i=1,j=1,sum=0;
    while(i<=l && j<=l){//田忌赛马
        if(n[i]>m[j]){//惩罚一次，下一张牌继续与他比较
            j++,sum++;
        }else{
            i++,j++;//若无，都换成下一张
        }
    }
    cout<<sum<<endl;
    i=1,j=1,sum=0;
    while(i<=l && j<=l){//重复
        if(n[i]<m[j]){
            sum++,i++,j++;
        }else{
            j++;
        }
    }
    cout<<sum;
    return 0;
}