D. River Locks #802 div2

Locks #802 div2"/>

D. River Locks #802 div2

Problem - D - Codeforces

题意是给你n个水坝和各自的容积，每个水坝上面都有一根水管可以放水，然后一秒钟放一升，问至少开多少个水管使得把n个水坝都装满的时间不得超过每次询问，一个i水坝装满之后，水可以流到i+1的水坝里面（不管高度）

做题一边读题一边想着有没有什么算法，时间长了之后就会知道什么题该用什么样的方法，不要什么题一上来就直接分析数据啥的，想一想学过的算法

这个题我一直沉浸在管子里的水是可以流的，然后不知道怎么办了，管他呢，流到哪跟我有什么关系吗，最后的题目是说流满需要多少个管子，那就看成一个整体啵，都是固定的。

假设全部管子都开着，这是所需要的最小时间了，容积是固定的，管子是固定的，相除就是最小时间了，假设某个询问小于这个数字，那直接输出-1

然后那具体开哪些个管子，在哪个上面开，管他呢，想那么多干啥啊，反正都是固定的，都是能流通的，只要关系式符合，那水怎么流，管子怎么放置就不需要关注了，因为每个管子的流速都是一样的，乘以时间，可以知道一共流了多少水，那就是二分呐，二分水管的数量，如果mid*x（x是时间，询问的时间）>=s[n]，那就是合法的。

判定二分边界：二分的是水管的数量，越往右边去，越是合法的：如果check函数合法，我想找到那个合法与不合法的边界，越往右边越合法，所以所需要的答案应该在左边，因此需要改变右边界，r=mid;l=mid+1;

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N];
int n;
bool check(ll mid,ll x)
{return mid*x>=a[n];
} 
int main(){cin>>n;ll maxn=-1;for(int i=1;i<=n;i++){cin>>a[i];a[i]+=a[i-1];maxn=max(maxn,(ll)ceil(a[i]*1.0/i));}
//	cout<<maxn<<endl;int Q;cin>>Q;while(Q--){int x;cin>>x;if(x<maxn){cout<<"-1"<<"\n";continue;} ll l=1,r=n;while(l<r){ll mid=l+r>>1;if(check(mid,x)) r=mid;else l=mid+1;}cout<<l<<"\n";}return 0;
}

多总结吧

二分：有二分查找，二分答案，在写题时我需要一个什么样的东西，并且序列是单调的，就可以试试二分。这个题我就是想知道有多少个水管，水管的数量也是从1到n，单调的。就可以想到二分了呀，用二分判断合不合法，找到那个最值（最值问题就可以想想二分，毕竟在边界上面，最大的最小值，最小的最大值），这个题就是要找最小需要的水管，就用了二分