CF [1700d] D. River locks (DP, bisection, Mathematics)

TP

Reference blog

Improved the details .

The question ：

• A large reservoir consists of n A volume of $vi$ Liters of water tank , Each water tank has a nozzle , Add one liter of water per second after opening . If the current tank i Full of , The extra water will be left supernaturally until i + 1 In the water tank , Until finally left to the sea .
• q Time to ask , One time at a time $tj$ , Ask to fill up in a given time n What is the minimum number of water inlets to be opened for each water tank , If the output cannot be filled -1.

Ideas ：

• obviously First step greedy , If you want to drive x A water outlet is opened in [1,x] , Drive ahead , After overflowing, the water can be replenished to the rear water tank , It takes less time to fill .
• The second step It is easy to deviate . In fact, two points will think , But I don't know how to do it . Here we should first derive a formula ：
• Assume that the total reservoir volume is known S, The given time limit is T; Within this time limit , The minimum number of nozzles to be opened has actually been determined ！, Number of open nozzles $cnt>=S/T$ （ Round up ）, Satisfy the minimum, so it is equal to ;
• cnt To determine the , Before, greed also knew that it was in front cnt individual , What remains to be determined is Before filling i Minimum time for one tank .
• therefore The third step , Set up dp state , Transfer , Plus binary optimization , The problem is solved .1900 Gold content of

Let's look at the notes

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define oper(a) operator<(const a& ee)const
#define endl '\n'
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e8;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
// Obviously greedy , The nozzle shall be opened in front as far as possible 
int v[N], dp[N];// Before opening  i  Water inlet , Before filling at the same time  i  The earliest time of a water tank 
ll sum[N];// Water volume prefix and 

void work() {
    
    dp[1] = v[1], sum[1] = v[1];
    for (int i = 2; i <= n; i++) {
    
        sum[i] = sum[i - 1] + v[i];

        //dp[i]  The earliest time is at least  dp[i-1], Fill in the front to cover the back 
        int l = dp[i - 1], r = 1e9;
        while (l < r)
        {
    
            int mid = l + r >> 1;
            //mid Is time ,i  Is the number of nozzles 
            if (1ll * mid * i < sum[i])l = mid + 1;
            else r = mid;
        }
        dp[i] = l;
    }
}

void solve() {
    
    cin >> n;
    forr(i, 1, n)cin >> v[i];
    work();

    // Clearly, what we require is the minimum number of outlets to fill the whole reservoir within a limited time , Why? dp This one is maintained ？

    // Because the total amount of the reservoir is known  S, Given the time limit  T;
    // Number of open nozzles  cnt >= S/T （ Round up ）, Satisfy the minimum, so it is equal to ;
    // 
    //  Meaning for ： After this open number is satisfied , The reservoir will certainly fill up , But the time is unknown ,
    //  Because of a single  vi  The limitation of .
    // 
    // After knowing the number of nozzles to be opened , We can substitute directly into  dp  Find the earliest time in , Just compare 

    cin >> m;
    while (m--)
    {
    
        int tim; cin >> tim;
        ll g = (sum[n] + tim - 1) / tim;

        if (g <= n && dp[g] <= tim)cout << g << endl;
        else cout << -1 << endl;
    }
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++)
        solve();
    return 0;
}
/* */