[ABC303F] Damage over Time题解

Assembly_line · 2023-05-29 21:18:55 · 题解

贪心地想，我们选 \max(d_i\times t_i) 肯定是最优的，因为这样可以打出最高的伤害。

有一种情况：当我们快把怪兽打完时，其实有时选 d_i 大的反而优，这是因为选 \max(d_i\times t_i) 时，可能这个技能时间打不完游戏已经结束了。

怎么判断何时打完怪兽呢？容易想到可以二分答案，然后把两种情况分开考虑。设当前的时间为 j，二分的答案为 k。

发现两种情况之间的转换只有可能是第一种情况转换为第二种情况，而转换的顺序是按照 t_i 由大到小的顺序，所以我们排序，维护前缀最大 d_i\times t_i 和后缀最大 d_i。

相邻的两个技能之间的时间段的情况是一样的，要一起处理了。

在两种情况中取最大值时，我们解一个不等式得到两种情况分别取的范围，有三种情况，判断一下即可。

时间复杂度 O(n\log V)。

#include<bits/stdc++.h>
#define ll __int128
const ll inf=1e18;
using namespace std;
int n;
ll h;
struct node{
    ll t,d;
}a[300003];
bool cmp(node x,node y){return x.t<y.t;}
ll maxn[300003],maxx;
ll read(){char ch=getchar();ll cnt=0;while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')cnt=(cnt<<3)+(cnt<<1)+ch-'0',ch=getchar();return cnt;}
void write(ll x){if(!x)return;write(x/10),putchar(x%10+'0');}
bool check(ll k)
{
    ll maxx=-inf,l=1,r,i=n,ans=0;
    for(;i>=1;i--)
    {
        if(a[i].t>k)maxx=max(maxx,a[i].d);
        else break;
    }
    for(;i>=1;i--)
    {
        r=k-a[i].t+1;
        if(maxx==-inf)ans+=(r-l+1)*maxn[i];
        else
        {
            ll p=maxn[i]/maxx,xr=k-l+1,xl=k-r+1;
            if(maxn[i]%maxx!=0)p++;
            if(p<=xl)ans+=maxx*(xl+xr)*(xr-xl+1)/2;
            else if(p>xr)ans+=maxn[i]*(xr-xl+1);
            else
            {
                ans+=maxx*(xr-p+1)*(xr+p)/2;
                ans+=maxn[i]*(p-xl);
            }
        }
        while(i>1&&a[i].t==a[i-1].t)maxx=max(maxx,a[i].d),i--;
        maxx=max(maxx,a[i].d);
        l=r+1;
    }
    ans+=maxx*(k-l+2)*(k-l+1)/2;
    return ans>=h;
}
int main()
{
    n=read(),h=read();
    for(int i=1;i<=n;i++)a[i].t=read(),a[i].d=read();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)maxn[i]=max(maxn[i-1],a[i].t*a[i].d);
    ll l=1,r=1e18,ans;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
    return 0;
}