對局匹配
原題目鏈接
題目描述
小明喜歡在一個圍棋網站上找別人在線對弈。這個網站上所有注冊用戶都有一個積分，代表他的圍棋水平。
小明發現，網站的自動對局系統在匹配對手時，只會將積分差恰好是 K 的兩名用戶匹配在一起。如果兩人分差小于或大于 K，系統都不會將他們匹配。現在小明知道，這個網站總共有 N 名用戶，以及他們的積分分別是 A?, A?, ..., A?。
小明想知道，最多可能有多少名用戶同時在線尋找對手，但系統卻一場對局都匹配不出來（即任意兩名用戶積分差不等于 K）？
輸入描述
- 第一行包含兩個整數
N和K。 - 第二行包含
N個整數A?, A?, ..., A?，表示每位用戶的積分。
數據范圍：
1 ≤ N ≤ 10?0 ≤ A? ≤ 10?0 ≤ K ≤ 10?
輸出描述
輸出一個整數，表示最多有多少名用戶無法被匹配（任意兩名用戶積分差不為 K）。
輸入樣例
10 0
1 4 2 8 5 7 1 4 2 8
輸出樣例
6
c++代碼
#include<bits/stdc++.h>using namespace std;int main() {int N, K, a, ans = 0;cin >> N >> K;vector<vector<int>> arr(K);vector<int> mid, mp(100005);for (int i = 0; i < N; i++) cin >> a, mid.push_back(a), mp[a]++;if (K == 0) {for (int i = 0; i <= 100004; i++) {if (mp[i] > 0) ans++;}cout << ans;return 0;}sort(mid.begin(), mid.end());for (int i = 0; i < N; i++) {if (arr[mid[i] % K].size() == 0 || arr[mid[i] % K].back() != mid[i] ) arr[mid[i] % K].push_back(mid[i]);}for (int i = 0; i < K; i++) {if (arr[i].size() == 0) continue;vector<int> dp(arr[i].size());dp[0] = mp[arr[i][0]];for (int j = 1; j < arr[i].size(); j++) {int b = j - 2 >= 0 ? dp[j - 2] : 0;if (arr[i][j] - arr[i][j - 1] == K) dp[j] = max(b + mp[arr[i][j]], dp[j - 1]);else dp[j] = dp[j - 1] + mp[arr[i][j]];}ans += dp[arr[i].size() - 1];}cout <<ans;return 0;
}//by wqs
題目解析
如果 k = 0，那么只用考慮總過出現了多少不同積分的用戶數，因為相同積分的用戶只能上線一個。
if (K == 0) {for (int i = 0; i <= 100004; i++) {if (mp[i] > 0) ans++;}cout << ans;return 0;
}
如果 k > 0，假設當前用戶積分為 x，則他能影響到的用戶積分為 x + k 和 x - k，又會因為積分為 x + k 用戶在線與否間接地影響到 x + 2k…可以發現積分對 k 求余相同的用戶可能會互相影響。如果積分對k 求余不相同，一點不會相互影響。
因此我們可以根據每個用戶積分對 k 求余的結果分成余數為 0 ~ k - 1 的組，共 k 組。此時我們只要解決每一組的最多在線人數最后求和即可。注意每一分組為了方便都從小到大排序。去重，出現次數用哈希表統計。
vector<vector<int>> arr(K);
for (int i = 0; i < N; i++) cin >> a, mid.push_back(a), mp[a]++;
sort(mid.begin(), mid.end());
for (int i = 0; i < N; i++) {if (arr[mid[i] % K].size() == 0 || arr[mid[i] % K].back() != mid[i] ) arr[mid[i] % K].push_back(mid[i]);
}
dp[i]表示當前分組前i個分最多可以選擇多少人
首先第i個分不會與第i - 2,i - 3,i - 4個分矛盾，因為i與i - 1起碼差K,i - 1與i - 2起碼差K，所以i與i - 2起碼差2 * K;
如果第i個分與第i - 1個分之差不為K,說明i個分與第i - 1個分不矛盾,他跟第i - 2,i - 3,i - 4個分也不矛盾，我們肯定要選上第i個分
dp[i] = dp[i - 1] + 第i個分的人數
如果第i個分與第i - 1個分之差為K,說明i個分與第i - 1個分矛盾,他跟第i - 2,i - 3,i - 4個分不矛盾，我們可以選擇第i個分不選第i - 1個分
dp[i] = dp[i - 2] + 第i個分的人數;
我們也可以選擇第i - 1個分不選第i個分;
dp[i] = dp[i - 1];
我們取最大值
dp[i] = max(dp[i - 2] + 第i個分的人數, dp[i - 1]);
vector<int> dp(arr[i].size());
dp[0] = mp[arr[i][0]];
for (int j = 1; j < arr[i].size(); j++) {int b = j - 2 >= 0 ? dp[j - 2] : 0;if (arr[i][j] - arr[i][j - 1] == K) dp[j] = max(b + mp[arr[i][j]], dp[j - 1]);else dp[j] = dp[j - 1] + mp[arr[i][j]];
}
對于每一分組，用ans累加就行
ans += dp[arr[i].size() - 1];
