2022/7/15 每日一题(二分+dp+贪心思维)

D. River Locks 难度：1900 题意：每个水闸都能城防一定体积容量的水，每秒注入1单位体积的水，若第i个水闸被注满，则自动流向第i+1水闸。每次询问给出一个时间，若能在规定时间内注满每个水闸，则最少需要打开多少个水闸。 思路：每个水闸会受到前面水闸容量的影响，不难看出使dp需要设计状态。 1.题目中没说一个水闸向另一个水闸转移的时间，所以可默认为0. 2.转移不需要时间，因此在左边选择开水闸的数据量即可，开启水口数cnt==(S/T)(向上取整) 3.我们知道规定时间内需要开启水闸的数量，但由于水闸的体积不同，并不知道填满前i个水箱的所需的具体时间，比如若总体积是15，规定在4秒前注满所有水箱，则需要开启水口数[15/4]=4，若前4个水闸体积分布4 1 5 4，需要4s；1 1 1 1需要1秒；6 1 1 1，则需要6s，不满足题意。 4.用dp的方式记录灌满前i个水闸需要的最小时间数，可看作一个约束条件，需要小于等于规定的时间。 5.二分的方式实现前i个水闸需要的最小时间，需要满足t*s>=sum[i]，s为开启 水闸数

代码： 要保证前i个水闸能在规定时间内t注满这个约束条件

#include
#define int long long
using namespace std;
const int N=1e6+6;
int n,v[N],dp[N],sum[N]; //注满前i个水闸至少需要多久
void pre()
{
    sum[1]=dp[1]=v[1];
    for(int i=2;in;
    for(int i=1;i>v[i];
    pre();
    int q;cin>>q;
    while(q--)
    {
        int ti;cin>>ti;
        int k=(sum[n]+ti-1)/ti;
        if(k