P10189 [USACO24FEB] Maximizing Productivity B 题解
先说说暴力做法：
每次遍历一遍，看看是否满足 ，满足就计数，不满足就挂。单次时间复杂度显然为 ，总得时间复杂度约为 ，TLE 是肯定的～
暴力代码：
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
|
#include <bits/stdc++.h>
#define log printf
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, q, c[N], t[N];
template <typename T>
inline T read() {
T sum = 0, fl = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T>
inline void write(T x) {
static T sta[35];
int top = 0;
do { sta[top++] = x % 10, x /= 10; } while (x);
while (top) putchar(sta[--top] + 48);
}
int main() {
n = read<int>(), q = read<int>();
FOR(i, 1, n) c[i] = read<int>();
FOR(i, 1, n) t[i] = read<int>();
FOR(i, 1, q) {
int v = read<int>(), s = read<int>(), cnt = 0;
FOR(j, 1, n) if (s + t[j] < c[j])++ cnt;
if (cnt >= v) puts("YES");
else puts("NO");
}
return 0;
}
|
评测记录 ，开了优化也只有
20pts。
暴力废了，开始整正解。
？二分法，了解一下？
然后，然后遇到了个问题：二分这东西要求有序，可是 与 是绑定在一起的啊！咋整？
注意 与
没关系，而这个式子能够求出啥啊？想要去到第 个农场最大的 嘛（，刚好卡点儿到，不可能再晚了）！
总结一下，问题相当于预处理出来一个数组 ，使 ，求数组中是否有至少 个数满足 。
先排个序（不然还是
嘛），然后就可以分出来两种做法：
做法一：二分，用
upper_bound 函数（因为是大于等于），时间复杂度约为 。
做法二：排完序后显然满足 ，因此如果 都小于等于
了，那它前面的自然也都满足。因此只需要判断 成不成立即可。时间复杂度约为
。
赛时 ACCode（做法二）:
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
|
#include <iostream>
#include <algorithm>
#define log printf
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;
int N, Q;
int close[200010], t[200010], ans[200010], V, S;
template <typename T>
inline T read() {
T sum = 0, fl = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T>
inline void write(T x) {
static T sta[35];
int top = 0;
do { sta[top++] = x % 10, x /= 10; } while (x);
while (top) putchar(sta[--top] + 48);
}
bool x(int a, int b) { return a > b; }
int main() {
cin >> N >> Q;
for (int i = 1; i <= N; i++) { cin >> close[i]; }
for (int i = 1; i <= N; i++) { cin >> t[i]; }
for (int i = 1; i <= N; i++) { ans[i] = close[i] - t[i]; }
sort(ans + 1, ans + N + 1, x);
while (Q--) {
cin >> V >> S;
if (ans[V] > S) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
|
AC 记录～
