BZOJ 4700: 适者（CDQ分治）

Posted On 2018年10月8日

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
【样例说明】
最好情况下，被秒杀的是敌方1、3号人形兵器，接下来需要5回合解决对方的2号人形兵器，对方共攻击4次，总计
造成28点伤害。可以证明没有更优的情况。

HINT

Source

Solution

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <iostream>
#define int long long
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=3e5+100;
struct mc{int a,d,delta;}store[maxn];
struct infoa{int delta,d;}a[maxn],tmpa[maxn];
struct infob{int delta,a,pos;}b[maxn],tmpb[maxn];
inline bool cmp(const mc&a,const mc&b){return a.a*b.d>b.a*a.d;}
int sigmaA[maxn],sigmaD[maxn],delta[maxn],f[maxn];
inline bool operator > (const infob&a,const infob&b){return a.a>b.a;}
inline bool operator < (const infoa&a,const infoa&b){return a.d==b.d?a.delta<b.delta:a.d<b.d;}
int n,atk;
void cdq(const int l,const int r)
{
	if (l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	static int Q[maxn];
	int front=1,rear=0;
	for (int i=l;i<=mid;i++)
	{
		while (front<=rear&&a[i].d==a[Q[rear]].d)--rear;
		while (front<rear&&(a[i].delta-a[Q[rear]].delta)*(a[Q[rear]].d-a[Q[rear-1]].d)>=((a[Q[rear]].delta-a[Q[rear-1]].delta))*(a[i].d-a[Q[rear]].d))--rear;
		Q[++rear]=i;
	}
	for (int i=mid+1;i<=r;i++)
	{
		while (front<rear&&b[i].a*(a[Q[front+1]].d-a[Q[front]].d)<=(a[Q[front+1]].delta-a[Q[front]].delta))
			++front;
		f[b[i].pos]=max(f[b[i].pos],a[Q[front]].delta+b[i].delta-b[i].a*a[Q[front]].d);
	}
	int p=l,q=mid+1,tot=l-1;
	while (p<=mid||q<=r)
	{
		if (p<=mid&&((a[p]<a[q]&&q<=r)||q>r))tmpa[++tot]=a[p++];
		else tmpa[++tot]=a[q++];
	}
	for (int i=l;i<=r;i++)a[i]=tmpa[i];
	p=l;q=mid+1;tot=l-1;
	while (p<=mid||q<=r)
	{
		if (p<=mid&&((b[p]>b[q]&&q<=r)||q>r))tmpb[++tot]=b[p++];
		else tmpb[++tot]=b[q++];
	}
	for (int i=l;i<=r;i++)b[i]=tmpb[i];
}
signed main()
{
	n=read(),atk=read();
	for (int i=1;i<=n;i++)
		store[i]=(mc){read(),read()},store[i].d=(store[i].d-1)/atk+1;
	sort(store+1,store+1+n,cmp);
	for (int i=1;i<=n;i++)
		sigmaA[i]=sigmaA[i-1]+store[i].a,
		sigmaD[i]=sigmaD[i-1]+store[i].d;
	for (int i=1;i<=n;i++)
		delta[i]=(sigmaD[i]-1)*store[i].a+(sigmaA[n]-sigmaA[i])*store[i].d;
	for (int i=1;i<=n;i++)
		a[i].delta=b[i].delta=delta[i],a[i].d=store[i].d,b[i].a=store[i].a,b[i].pos=i;
	ll sum=0,ans=0;
	for (int i=1;i<=n;i++)
		sum+=(sigmaD[i]-1)*store[i].a;
	cdq(1,n);
	for (int i=1;i<=n;i++)
		ans=max(ans,f[i]);
	printf("%lld\n",sum-ans);
}

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <bitset>

#include <algorithm>

#include <cstdlib>

#include <set>

#include <queue>

#include <iostream>

#define int long long

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=3e5+100;

struct mc{int a,d,delta;}store[maxn];

struct infoa{int delta,d;}a[maxn],tmpa[maxn];

struct infob{int delta,a,pos;}b[maxn],tmpb[maxn];

inline bool cmp(const mc&a,const mc&b){return a.a*b.d>b.a*a.d;}

int sigmaA[maxn],sigmaD[maxn],delta[maxn],f[maxn];

inline bool operator > (const infob&a,const infob&b){return a.a>b.a;}

inline bool operator < (const infoa&a,const infoa&b){return a.d==b.d?a.delta<b.delta:a.d<b.d;}

int n,atk;

void cdq(const int l,const int r)

{

if (l==r)return;

int mid=(l+r)>>1;

cdq(l,mid);cdq(mid+1,r);

static int Q[maxn];

int front=1,rear=0;

for (int i=l;i<=mid;i++)

{

while (front<=rear&&a[i].d==a[Q[rear]].d)--rear;

while (front<rear&&(a[i].delta-a[Q[rear]].delta)*(a[Q[rear]].d-a[Q[rear-1]].d)>=((a[Q[rear]].delta-a[Q[rear-1]].delta))*(a[i].d-a[Q[rear]].d))--rear;

Q[++rear]=i;

}

for (int i=mid+1;i<=r;i++)

{

while (front<rear&&b[i].a*(a[Q[front+1]].d-a[Q[front]].d)<=(a[Q[front+1]].delta-a[Q[front]].delta))

++front;

f[b[i].pos]=max(f[b[i].pos],a[Q[front]].delta+b[i].delta-b[i].a*a[Q[front]].d);

}

int p=l,q=mid+1,tot=l-1;

while (p<=mid||q<=r)

{

if (p<=mid&&((a[p]<a[q]&&q<=r)||q>r))tmpa[++tot]=a[p++];

else tmpa[++tot]=a[q++];

}

for (int i=l;i<=r;i++)a[i]=tmpa[i];

p=l;q=mid+1;tot=l-1;

while (p<=mid||q<=r)

{

if (p<=mid&&((b[p]>b[q]&&q<=r)||q>r))tmpb[++tot]=b[p++];

else tmpb[++tot]=b[q++];

}

for (int i=l;i<=r;i++)b[i]=tmpb[i];

}

signed main()

{

n=read(),atk=read();

for (int i=1;i<=n;i++)

store[i]=(mc){read(),read()},store[i].d=(store[i].d-1)/atk+1;

sort(store+1,store+1+n,cmp);

for (int i=1;i<=n;i++)

sigmaA[i]=sigmaA[i-1]+store[i].a,

sigmaD[i]=sigmaD[i-1]+store[i].d;

for (int i=1;i<=n;i++)

delta[i]=(sigmaD[i]-1)*store[i].a+(sigmaA[n]-sigmaA[i])*store[i].d;

for (int i=1;i<=n;i++)

a[i].delta=b[i].delta=delta[i],a[i].d=store[i].d,b[i].a=store[i].a,b[i].pos=i;

ll sum=0,ans=0;

for (int i=1;i<=n;i++)

sum+=(sigmaD[i]-1)*store[i].a;

cdq(1,n);

for (int i=1;i<=n;i++)

ans=max(ans,f[i]);

printf("%lld\n",sum-ans);

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments