Znzryb's Blog
0%

CF-1004-B. Two Large Bags

Posted on Edited on

思路讲解

https://codeforces.com/blog/entry/139415?locale=en

基本就是官方题解的思路

我们可以证明可以进行二操作的时候一定是先进行二操作的（说白了就那些数，+1了总归和后面相等的概率大一点），而不是先进行一操作

把所有2操作进行完了再进行1操作，我们可以证明，我们一定要将一个等于a1的数字发送到bag B，否则B中所有数字都大于a1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (idx <= N - 1) {
  if (A[idx] != A[idx + 1]) {
    cout << "No\n";
    return;
  } else {
    vis[A[idx + 1]] = true;
    idx += 2;  // 相当于将idx以及idx+1锁住(idx是因为要满足idx+1的需求，idx+1是因为移入了B)
    FOR(i, idx, N) {
      if (vis[A[i]]) {
        A[i] += 1;
      } else {
        break;
      }
    }
  }
// #ifdef LOCAL
  // FOR(i, 1, N) { cerr << A[i] << ' '; }
  // cerr << '\n';
// #endif
}
cout << "Yes\n";
}

AC代码

https://codeforces.com/contest/2067/submission/305772242

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// Problem: B. Two Large Bags
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(1e3) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, A[MAXN], vis[MAXN];

inline void solve() {
  cin >> N;
  FOR(i, 1, N) {
    cin >> A[i];
    vis[i] = false;  // B这个袋子里有没有这个数字？
  }
  sort(A + 1, A + 1 + N);
  ll idx = 1;
  while (idx <= N - 1) {
    if (A[idx] != A[idx + 1]) {
      cout << "No\n";
      return;
    } else {
      vis[A[idx + 1]] = true;
      idx += 2;  // 相当于将idx以及idx+1锁住
      FOR(i, idx, N) {
        if (vis[A[i]]) {
          A[i] += 1;
        } else {
          break;
        }
      }
    }
// #ifdef LOCAL
    // FOR(i, 1, N) { cerr << A[i] << ' '; }
    // cerr << '\n';
// #endif
  }
  cout << "Yes\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
// #ifdef LOCAL
    // cerr << '\n';
// #endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305772242
*/

心路历程（WA，TLE，MLE……）