BZOJ 4700: 适者

敌方有 n 台人形兵器，每台的攻击力为 Ai，护甲值为 Di。我方只有一台人形兵器，攻击力为 ATK。战斗看作回合制， 每回合进程如下：
·1 我方选择对方某台人形兵器并攻击，令其护甲值减少 ATK，若护甲值<0 则被破坏。
·2 敌方每台未被破坏的人形兵器攻击我方基地造成 Ai 点损失。
但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损 失。

Input

第一行两个数 n，ATK，表示敌方人形兵器数量和我方人形兵器攻击力。
接下来 n 行，每行两个数 A，Di，表示对方第 i 台人形兵器的攻击力和护甲值。
3<=n<=3×10^5，Ai，Di<=10^4，ATK<10^4

Output

只一行，一个数，表示最好情况下我方基地会受到的损失总和。

Sample Input

3 7
30 8
7 35
1 209

Sample Output

28

Solution

每个敌人被杀所需时间为 $T_i=D_i/atk+1$。
设 T 的前缀和为 P，A 的后缀和为 S。
假设没有秒杀，按 $T_i/A_i$ 排序后依次杀即可，每个敌人对答案的贡献为 $S_i\cdot T_i-A_i$。
假设（排序后）秒杀了 i 和 j（假设 $i<j$），那么我方损失会减少 $S_i\cdot T_i + P(i-1)\cdot A_i - A_i + S_j\cdot T_j + P(j-1)\cdot A_j - A_j - T_i\cdot A_j$。
注意最后 $-T_i\cdot A_j$ 是因为算了两次。
由于只有 $T_i\cdot A_j$ 与 $i,j$ 均有关，这个表达式可以看成一个以 $T_i$ 为变量的一次函数。
若从后往前扫，就可以看成动态维护一些直线的凸包。
这个用线段树就可以维护，每个节点存一条直线，标记永久化。
修改时，找到两直线交点，把距端点更短的一部分 pushdown。
查询时把路径上所有节点取 max。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))

struct line
{
    ll k,b;
}s[35000];

void modify(int x,int l,int r,line p)
{
    if(s[x].k==p.k)
    {
        repr(s[x].b,p.b);
        return;
    }
    int t=(l+r)>>1;
    db f=(db)(p.b-s[x].b)/(s[x].k-p.k);
    if(f<l||f>r||l==r)
    {
        if(p.k*t+p.b>s[x].k*t+s[x].b)s[x]=p;
        return;
    }
    if(f<t+0.5)
    {
        if(p.k*r+p.b>s[x].k*r+s[x].b)std::swap(s[x],p);
        modify(x<<1,l,t,p);
    }
    else
    {
        if(p.k*l+p.b>s[x].k*l+s[x].b)std::swap(s[x],p);
        modify(x<<1|1,t+1,r,p);
    }
}

ll query(int x,int l,int r,int p)
{
    ll ret=s[x].k*p+s[x].b;
    if(l!=r)
    {
        int t=(l+r)>>1;
        if(p<=t)
            repr(ret,query(x<<1,l,t,p));
        else
            repr(ret,query(x<<1|1,t+1,r,p));
    }
    return ret;
}

struct yjq
{
    int a,t;
    ll as,tp;
    inline bool operator <(const yjq &x)const
    {
        return (ll)x.a*t<(ll)a*x.t;
    }
}p[300000];

int n,atk;

int main()
{
    scanf("%d%d",&n,&atk);
    for(int i=0;i<n;i++)
        scanf("%d%d",&p[i].a,&p[i].t),p[i].t=(p[i].t-1)/atk+1;
    std::sort(p,p+n);
    for(int i=1;i<n;i++)
        p[i].tp=p[i-1].tp+p[i-1].t;
    p[n-1].as=p[n-1].a;
    for(int i=n-2;i>=0;i--)
        p[i].as=p[i+1].as+p[i].a;
    for(int i=0;i<35000;i++)
        s[i].b=-1e18;
    ll ta=0;
    for(int i=n-1;i>=0;i--)
    {
        ll tmp=p[i].as*p[i].t+p[i].tp*p[i].a-p[i].a;
        repr(ta,query(1,1,10000,p[i].t)+tmp);
        modify(1,1,10000,(line){-p[i].a,tmp});
    }
    ll ans=0;
    for(int i=0;i<n;i++)
        ans+=p[i].as*p[i].t-p[i].a;
    ans-=ta;
    printf("%lld\n",ans);
}

日期： 2016-12-01

标签： BZOJ 贪心 线段树

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/90/ 查看。