今日学习记录
1. https://codeforces.com/contest/2158/problem/B
关键词：贪心
问题分析：
就是给出一个 2n 长度的数组,然后要把数组分成两个长度相等且为 n 的子数组,不能重合,要使两个数组中的出现次数为奇数的不同元素个数相加结果最大,输出最大值
核心思路:
先使用哈希表统计不同元素的出现次数,然后考虑怎么分配元素使两个数组的值最大
其实好思考,只有奇数能提供贡献,所以对出现次数进行奇偶讨论,我们要这些次数分配成两个 n 的数组,且无论怎么分配,就是要最后总和的贡献最大
对于总出现次数,奇数能分为奇数+偶数贡献为 1,偶数能分为奇数+奇数贡献为 2,且偶数是对称存在的,所以我们先考虑偶数,再考虑奇数(因为奇数单个存在,好用于填补)
接下来就是考虑如何分为两个为 n 的情况
一个偶数分为两个奇数,这两者的差值也为偶数,所以这两个数会造成两个数组的值差,但是我们通过贪心想,我们尽量将该偶数分的平均点,偶数 = r-l+2,这样偶数总差二,下面的偶数又可以补,而奇数又可以分为奇数和偶数,奇数无论放在哪里,偶数又可以去填补,所以无需过于复杂的讨论,就是看出现次数为奇数的有多少,偶数有多少
分为两个情况
有奇数次的时候,贡献就等于偶数次 x2+奇数次(偶数次不能超过 n)
无奇数次的时候,这个时候就要想怎么分配偶数次,偶数次还要平均的为成 n 份,所以要与 n 同奇偶且不能小于 0,贡献为 2x 偶数次
**最终代码：
#include <bits/stdc++.h>
using namespace std;
#define ve vector
using ll = long long;
using ull = unsigned long long;
using sr = string;
using db = double;
const int MOD=998244353;
const ll INF=1e18;
const int DIR[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
int T;
void solve(){
int n;cin>>n;
unordered_map<int,int> mp;
for(int i = 0;i<n*2;i++){
int m;cin>>m;
mp[m]++;
}
int one = 0,two = 0;
for(auto [a,b]:mp){
if(b%2) one++;
else two++;
}
ll ans = 0;
if(one>0){
int t = min(n,two);
ans = one+2LL*t;
}else{
int t = min(two,n);
if((t%2)!=(n%2)) t--;
if(t<0) t = 0;
ans = 2LL*t;
}
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while(T--) solve();
return 0;
}学到的点： 1.