[Tmt514] Beverage Cup 2 B - Dreamoon's Criterion

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

夢月解題目會根據夢月法則?如果題目需要花費大於等於 t 的時間,則定義題目難度為 hard,反之為 easy。小番茄 (求解釋) 準備 n 個題目請求夢月協助,但隨著每解一題,下一題的難度會隨著疲累值增加,疲累值為一個等差為 k 個數列。只打算解決 easy 的題目,請問在相同的 k 下,不同的 t 分別能解決的最多題數。

Sample Input

1
2
3
4
5
6
1
5 2
7 3 6 8 5
2
9
1

Sample Output

1
2
4
0

Solution

t 越大,能解的題目肯定越多!難度越低的題目一定會選,因此前 i 小難度的題目都會被挑。利用類似求方程式值的方式 (隨便講講,別太在意 f(x) = a0 + a1x + a2x^2 + a3x^3 … + anx^n,可以在 O(n) 完成的方法) 下去猜測?維護已選題目如果增加 k 不大於 t 且下一個題目難度也小於 t,則所有已選難度都增加 k!離線處理,將詢問的 t 由小到大排序,掃描過去?

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 131072;
int A[MAXN], Qt[MAXN], out[MAXN];
int main() {
int testcase;
int N, K, Q;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &N, &K);
for (int i = 0; i < N; i++)
scanf("%d", &A[i]);
scanf("%d", &Q);
for (int i = 0; i < Q; i++)
scanf("%d", &Qt[i]);

vector< pair<int, int> > QV;
for (int i = 0; i < Q; i++)
QV.push_back(make_pair(Qt[i], i));

sort(QV.begin(), QV.end());
sort(A, A+N);

int idx = -1, sum = 0, t, mx = -0x3f3f3f3f;
for (int i = 0; i < Q; i++) {
t = QV[i].first;
while (idx+1 < N && mx + K <= t && A[idx+1] <= t) {
idx++, sum++;
mx = max(mx+K, A[idx]);
}
out[QV[i].second] = sum;
}

for (int i = 0; i < Q; i++)
printf("%d\n", out[i]);
}
return 0;
}

/*
1
5 2
7 3 6 8 5
2
9
1
*/