题解：P8267 [USACO22OPEN] Counting Liars B & U208878 晴天

1
// Problem: P8267 [USACO22OPEN] Counting Liars B
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P8267
4
// Memory Limit: 256 MB
5
// Time Limit: 2000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<int, int> PII;
26

27
const int N = 1010;
28
int n, t[N], ans = INF;
29
vector<int> pls;
30
char op[N];
31

32
template <typename T>
33

34
inline T read() {
35
  T sum = 0, fl = 1;
36
  char ch = getchar();
37
  for (; !isdigit(ch); ch = getchar())
38
    if (ch == '-') fl = -1;
39
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
40
  return sum * fl;
41
}
42

43
template <typename T>
44

45
inline void write(T x) {
46
  if (x < 0) {
47
    putchar('-'), write<T>(-x);
48
    return;
49
  }
50
  static T sta[35];
51
  int top = 0;
52
  do { sta[top++] = x % 10, x /= 10; } while (x);
53
  while (top) putchar(sta[--top] + 48);
54
}
55

56
int main() {
57
  IOS cin >> n;
58
  FOR(i, 1, n) {
59
    cin >> op[i] >> t[i];
60
    pls.push_back(t[i]);  // 数组 p
61
  }
62
  unique(pls.begin(), pls.end());  // 去重
63
  for (auto i : pls) {
64
    int tmp = 0;
65
    FOR(j, 1, n) if ((op[j] == 'L' && i > t[j]) || (op[j] == 'G' && i < t[j]))++ tmp;  // 满足条件就过
66
    ans = min(ans, tmp);
67
  }
68
  write<int>(ans);
69
  return 0;
70
}

1
// Problem: U208878 晴天
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/U208878
4
// Memory Limit: 128 MB
5
// Time Limit: 1000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<int, int> PII;
26

27
const int N = 2e5 + 10;
28
int n, t, ans = INF;
29
vector<int> pls, lhs, rhs;
30
char op;
31

32
template <typename T>
33

34
inline T read() {
35
  T sum = 0, fl = 1;
36
  char ch = getchar();
37
  for (; !isdigit(ch); ch = getchar())
38
    if (ch == '-') fl = -1;
39
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
40
  return sum * fl;
41
}
42

43
template <typename T>
44

45
inline void write(T x) {
46
  if (x < 0) {
47
    putchar('-'), write<T>(-x);
48
    return;
49
  }
50
  static T sta[35];
51
  int top = 0;
52
  do { sta[top++] = x % 10, x /= 10; } while (x);
53
  while (top) putchar(sta[--top] + 48);
54
}
55

56
int main() {
57
  IOS cin >> n;
58
  FOR(i, 1, n) {
59
    cin >> op >> t;
60
    pls.push_back(t);
61
    if (op == 'L') lhs.push_back(t);
62
    else rhs.push_back(t);
63
  }
64
  sort(pls.begin(), pls.end());
65
  sort(lhs.begin(), lhs.end());
66
  sort(rhs.begin(), rhs.end());
67
  for (auto i : pls) {
68
    int tmpg = rhs.size() - (upper_bound(rhs.begin(), rhs.end(), i) - rhs.begin()), tmpl = lower_bound(lhs.begin(), lhs.end(), i) - lhs.begin();
69
    cerr << i << ' ' << tmpg << ' ' << tmpl << endl;
70
    ans = min(ans, tmpg + tmpl);
71
  }
72
  write<int>(ans);
73
  return 0;
74
}