“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛——E.赛马【贪心 nlogn】

题目传送门

题解

• 每次暴力寻找比 $b[i]$ 大且没参赛过的最小 $a[j]$ 值$（1<=i<=n，1<=j<=n）$。时间复杂度$O(n^2)$。

• 将 $a[i]$ 和 $b[i]$ 数组放到一起排序，每次按照最大括号匹配的方式计算。时间复杂度 $O(nlogn)$。

AC-Code

#include <bits/stdc++.h>
using namespace std;struct NODE {
    bool flag;int val;
}f[1005 << 1];bool cmp(NODE a, NODE b) {
        // 返回true调换位置if(a.val != b.val)    return a.val < b.val;    // 战力值升序else     return a.flag;    // 田忌的靠后
}int main() {
    int t;    cin >> t;while(t--) {
    int n;    cin >> n;for(int i = 0; i < n; ++i) {
    cin >> f[i].val;f[i].flag = true;}for(int i = 0; i < n; ++i) {
    cin >> f[i + n].val;f[i + n].flag = false;}sort(f, f + n * 2, cmp);int ans = 0, pre = 0;for(int i = 0; i < n * 2; ++i) {
    if(f[i].flag == false) ++pre;else if(pre > 0)--pre, ++ans;}cout << ans << endl;}
}