mcfx's blog - 贪心

mcfx's blog - 贪心 2016-12-01T20:46:00+08:00 Typecho /feed/atom/category/tx/ <![CDATA[BZOJ 4700: 适者]]> /archives/90/ 2016-12-01T20:46:00+08:00 2016-12-01T20:46:00+08:00 admin

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

###Code
```c++
#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);
}
```

]]>