傳送門

題意：

定義第$i$個(gè)數(shù)是$a+(i?1)?b$，先有$q$個(gè)詢問，每次詢問給你$l,t,m$代表你可以操作$t$次，每次可以將最多$m$個(gè)數(shù)減$1$，每次都需要回答從$l$開始， 最遠(yuǎn)到第幾個(gè)數(shù)，能在執(zhí)行完這些操作之后$[l,r]$內(nèi)的數(shù)被減成$0$。

$1\le a,b\le 1e6,1\le q\le 1e5,1\le l,t,m\le 1e6$

思路：

顯然可以二分$r$的位置，讓后考慮怎么檢查答案。

這里有個(gè)結(jié)論，判斷這個(gè)區(qū)間是否能都被減到$0$需要滿足以下兩個(gè)條件：

$[l,r]$內(nèi)數(shù)的和$\le t?m$

$r$位置的數(shù)需要$\le t$

第二個(gè)顯然，第一個(gè)背過就行。。

關(guān)于第一個(gè)的證明，$lc$有一個(gè)類似的題，貼個(gè)個(gè)鏈接：

鏈接

這個(gè)題的模型就是有$m$個(gè)電池，每個(gè)電池都有容量$c_i$，有$n$個(gè)電腦，每個(gè)電腦每分鐘都需使用某個(gè)電池的一個(gè)電量，問能使所有電腦都正常運(yùn)行的最長(zhǎng)時(shí)間是多少。

這個(gè)題就是二分最長(zhǎng)時(shí)間，設(shè)$sum=\sum min(c_i,mid)$，那么電腦能運(yùn)行$mid$分鐘的充要條件就是$mid?n\le sum$。

#include<bits/stdc++.h> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;LL a,b,n;LL get(LL l,LL r) {LL n=r-l+1;LL st=a+(l-1)*b;LL ed=a+(r-1)*b;return n*(st+ed)/2; }void solve() {cin>>a>>b>>n;while(n--) {LL l,t,m;scanf("%lld%lld%lld",&l,&t,&m);LL ls=l,rs=1e9,ans=-1;while(ls<=rs) {LL mid=ls+rs>>1;if(get(l,mid)<=t*m&&a+(mid-1)*b<=t) ans=mid,ls=mid+1;else rs=mid-1;}printf("%lld\n",ans);} }int main() {int _=1;while(_--) {solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF535C Tavas and Karafs 二分 + 结论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。