[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
5 2
7 3 6 8 5
2
9
1

Sample Output

4
0

Solution

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

#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
*/