P10189 [USACO24FEB] Maximizing Productivity B 题解

先说说暴力做法：

每次遍历一遍，看看是否满足 $t_i + s \le c_i$ ，满足就计数，不满足就挂。单次时间复杂度显然为 $O(N)$ ，总得时间复杂度约为 $O(NQ)$ ，TLE 是肯定的~

暴力代码：

1
// Problem: Problem 3. Maximizing Productivity
2
// Contest: USACO - USACO 2024 February Contest, Bronze
3
// URL: https://usaco.org/index.php?page=viewproblem&cpid=1385
4
// Memory Limit: 256 MB
5
// Time Limit: 4000 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, q, c[N], t[N];
29

30
template <typename T>
31

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

41
template <typename T>
42

43
inline void write(T x) {
44
  static T sta[35];
45
  int top = 0;
46
  do { sta[top++] = x % 10, x /= 10; } while (x);
47
  while (top) putchar(sta[--top] + 48);
48
}
49

50
int main() {
51
  n = read<int>(), q = read<int>();
52
  FOR(i, 1, n) c[i] = read<int>();
53
  FOR(i, 1, n) t[i] = read<int>();
54
  FOR(i, 1, q) {
55
    int v = read<int>(), s = read<int>(), cnt = 0;
56
    FOR(j, 1, n) if (s + t[j] < c[j])++ cnt;
57
    if (cnt >= v) puts("YES");
58
    else puts("NO");
59
  }
60
  return 0;
61
}

评测记录，开了优化也只有 20pts。

暴力废了，开始整正解。

$2 \times 10^5$ ？二分法，了解一下？

然后，然后遇到了个问题：二分这东西要求有序，可是 $c_i$ 与 $t_i$ 是绑定在一起的啊！咋整？

注意 $c_i$ 与 $c_i - t_i$ 没关系，而这个式子能够求出啥啊？想要去到第 $i$ 个农场最大的 $S$ 嘛（ $c_i - t_i + t_i = c_i$ ，刚好卡点儿到，不可能再晚了）！

总结一下，问题相当于预处理出来一个数组 $a$ ，使 $a_i = c_i - t_i$ ，求数组中是否有至少 $V$ 个数满足 $a_i \ge S$ 。

先排个序（不然还是 $O(n)$ 嘛），然后就可以分出来两种做法：

做法一：二分，用 upper_bound 函数（因为是大于等于），时间复杂度约为 $O(QlogN)$ 。

做法二：排完序后显然满足 $a_V \ge a_{V - 1} \ge a_{V - 2} ... a_1$ ，因此如果 $a_V$ 都小于等于 $S$ 了，那它前面的自然也都满足。因此只需要判断 $a_V \ge S$ 成不成立即可。时间复杂度约为 $O(Q)$ 。

赛时 ACCode（做法二）:

1
// Problem: Problem 3. Maximizing Productivity
2
// Contest: USACO - USACO 2024 February Contest, Bronze
3
// URL: https://usaco.org/index.php?page=viewproblem&cpid=1385
4
// Memory Limit: 256 MB
5
// Time Limit: 4000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <iostream>
11
#include <algorithm>  // 万能头CE
12

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

22
using namespace std;
23

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

28
int N, Q;
29
int close[200010], t[200010], ans[200010], V, S;
30

31
template <typename T>
32

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

42
template <typename T>
43

44
inline void write(T x) {
45
  static T sta[35];
46
  int top = 0;
47
  do { sta[top++] = x % 10, x /= 10; } while (x);
48
  while (top) putchar(sta[--top] + 48);
49
}
50

51
bool x(int a, int b) { return a > b; }
52

53
int main() {
54
  cin >> N >> Q;
55
  for (int i = 1; i <= N; i++) { cin >> close[i]; }
56
  for (int i = 1; i <= N; i++) { cin >> t[i]; }
57
  for (int i = 1; i <= N; i++) { ans[i] = close[i] - t[i]; }
58
  sort(ans + 1, ans + N + 1, x);
59
  while (Q--) {
60
    cin >> V >> S;
61
    if (ans[V] > S) cout << "YES" << endl;
62
    else cout << "NO" << endl;
63
  }
64
  return 0;
65
}

AC记录~

音乐

音乐

支持与分享

评论区