题解：P11782 [JOIGST 2024] 卡牌游戏 / Card Game 3

Solution

首先考虑没有不同色的限制怎么做，显然就是让 $i$ 选择点数最大的卡牌，$j$ 选所有其他的卡牌，如果 $a_i + a_j > 0$ 就加上这个贡献。

加上限制之后，和最大卡牌异色的我们可以用上面的方法处理。考虑和最大卡牌同色的卡牌怎么办？选择和最大卡牌异色的最大的卡牌，让 $i$ 选它，$j$ 选所有和最大卡牌同色的卡牌即可。

Code

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define REP(i, l, r, k) for (int i = (l); i <= (r); i += k)
#define PER(i, l, r, k) for (int i = (l); i >= (r); i -= k)
#define ls x << 1
#define rs x << 1 | 1
#define umap unordered_map
#define uset unordered_set
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define x1 Sun
#define y1 Jude
void ckmin(int &x, int y) { x = std::min(x, y) ; }
void ckmax(int &x, int y) { x = std::max(x, y) ; }
int lowbit(int x) { return x & -x ; }

using namespace std;

const int maxn = 5e5 + 5 ;
// const int inf = ;
// const int mod = ; 

int n ; 
struct Node {
    int a, c ;
    bool operator < (const Node &y) const {
        return a > y.a ;
    }
} a[maxn] ;

void solve(){
    cin >> n ;
    rep(i, 1, n) {
        cin >> a[i].a >> a[i].c ;
    }
    sort(a + 1, a + 1 + n) ;
    int id = -1 ;
    rep(i, 2, n) {
        if(a[i].c != a[1].c) {
            id = i ; 
            break ;
        }
    }
    int ans = 0 ;
    rep(i, 2, n) {
        if(a[i].c != a[1].c) {
            ans += max(a[i].a + a[1].a, 0ll) ;
        }
    }
    if(id != -1) {
        rep(i, 2, n) {
            if(a[i].c == a[1].c) {
                ans += max(a[id].a + a[i].a, 0ll) ;
            }
        }
    }
    cout << ans << endl ;
    return ;
}
signed main(){
    // freopen("yoxi.in", "r", stdin) ;
    // freopen("yoxi.out", "w", stdout) ;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
//  cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
}

---

• 分类： OI
• 标签： 无标签