Sample Input
3
4 4
2 4 3 1
4 3
1 3 4
4 3
2 3 4

Sample Output
YES
YES
NO

題意 ：

• 將1 - n的n個整數(shù)分成m個集合，滿足第i個集合的中位數(shù)為bi，求是否存在解。中位數(shù)定義為c[(k + 1) / 2]，相當(dāng)于123中的2或者1234中的2

思路 ：

• 顯然b數(shù)組的m個數(shù)放在m個集合，剩下的n - m個數(shù)要放到這m個集合中且不影響原本的中位數(shù)。比如對于樣例n = 6， m = 2，b = {3, 5}時，集合被分為[1,2], [4], [6]三段。且任意兩段中的一對數(shù)字可以被配對消掉，以及最后剩下來的數(shù)字一定是同一段內(nèi)的。
• 如果長度最大的段的長度mx <= 其他段數(shù)之和sum，直接輸出YES，反之，那么這一段最后會剩下數(shù)字，此時當(dāng)且僅當(dāng)這一段左邊的集合（中位數(shù)小于這一段的中位數(shù)）個數(shù) 大于等于 這一段剩下的數(shù)字的個數(shù) 時（把剩下的數(shù)字放在分別放在左邊那幾個集合的右邊，利用1234中2是中位數(shù)的性質(zhì)），為YES，否則為NO

#include <iostream> #include <algorithm> #include <vector>#define x first #define y secondusing namespace std;typedef long long LL;const int N = 1e5 + 10;int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T;cin >> T;while (T -- ){int n, m;cin >> n >> m;vector<int> a(n + 10); // 如果使用數(shù)組每次還要memset，且多開更多空間，不如還是vectora[n + 1] = 1; // wa，因為是通過斷點求區(qū)間，否則最后一個區(qū)間就沒有了for (int i = 1; i <= m; i ++ ){int x;cin >> x;a[x] = 1;}vector<pair<int, int>> vc; // 這個區(qū)間的長度，左邊有幾個區(qū)間int len = 0, cnt = 0, sum = 0;for (int i = 1; i <= n + 1; i ++ ) // wa，要到n + 1，因為是斷點判斷區(qū)間{if (!a[i]) len ++ ;else{if (len != 0) // wa，可能一開始就是點{vc.push_back({len, cnt});sum += len;}cnt ++ , len = 0;}}if (n == m){cout << "YES" << endl;continue;}sort(vc.begin(), vc.end());int mx = vc.back().x, ed = vc.back().y;if ((mx <= sum - mx) || (ed >= mx - (sum - mx))) cout << "YES" << endl;else cout << "NO" << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Median断点法求区间-匹配-memset数组与vector的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。