这种思路对吗
查看原帖
这种思路对吗
674793
luoguhandongheng楼主2025/7/18 09:37

代码是 A 了,但不知道思路是否正确。

对于我方序列 a 和敌方序列 b,都考虑升序排序。然后双指针,如果 ai>bj+1a_i > b_{j + 1} 那么分数加 2,jj+1j \gets j + 1。否则看一下之前有没有小于自己平局的,如果有就去替换以前的,将平局变成胜利,分数加一。如果没有,再看如果 ai=bj+1a_i = b_{j + 1} 那么分数加 1,jj+1j \gets j + 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N], b[N], n;
int solve(int x[], int y[]){
    int j = 0, cnt = 0, lstc = 0, nowc = 0;
    for(int i = 1; i <= n; ++i){
        if(x[i] != x[i - 1]) lstc += nowc, nowc = 0;
        if(j < n && y[j + 1] < x[i]) ++j, cnt += 2;
        else{
            if(lstc) --lstc, cnt++;
            else if(j < n && y[j + 1] == x[i]) ++j, nowc++, cnt++;
        }
        //debug(i, j, cnt, lstc, nowc);
    }
    return cnt; 
}
int main(){
    cin.tie(0)->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);
    //debugArr(a, n + 1);
    //debugArr(b, n + 1);
    cout << solve(a, b) << ' ' << 2 * n - solve(b, a);
    return 0;
}
2025/7/18 09:37
加载中...