【BZOJ 4700】适者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4700
神犇题解:http://blog.csdn.net/werkeytom_ftd/article/details/54565251

解题报告

设第$i$个机器人打$t_i$次就会$GG$,攻击力是$v_i$
那么推推式子发现$i$比$j$先死更优,当且仅当$t_iv_j < t_jv_i$
于是我们先排个序,贪一贪心

现在考虑如何一开始就$GG$掉的两个,因为删除之后不会影响决策
所以我们相当于在贪心后的删除序列上再删掉两个点
考虑删掉的第一个点对于第二个点的贡献,形如$av_i+b$
这是一个直线的表达式,于是相当于让你维护一个数据结构,支持插入直线、查询单点最值
这个是一个经典的数据结构问题,可以用李超树来解决
总时间复杂度:$O(n \log n)$

另外,这题还有CDQ分治的做法,时间复杂度仍然为$O(n \log n)$
再另外,我居然暂时是$Rank \ 1$!第一次$Rank \ 1$啊! ★,°:.☆( ̄▽ ̄)/$:.°★

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int INF = 10000;
const double EPS = 1e-6;

int n,ATK; LL sum[N],pre[N],vout,ans;
struct ROB{int t,v;}r[N];
inline bool cmp(const ROB &A, const ROB &B) {return (LL)A.t * B.v < (LL)B.t * A.v;} 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Segment_Tree{
	int root,cnt; LL AnsTmp;
	struct Node{int ch[2],a; LL b,pl,pr;double pm;}p[N<<1];
	public:
		inline void insert(int a, LL b) {
			insert(root, 1, INF, a, b);
		}
		inline LL query(int x) {
			AnsTmp = 0;
			query(root, 1, INF, x);
			return AnsTmp;
		}
	private:
		void insert(int &w, int l, int r, int a, LL b) {
			if (!w) w = ++cnt;
			if (!p[w].a) {p[w].a = a, p[w].b = b; return;}
			LL nl = (LL)a*l+b, nr = (LL)a*r+b; 
			double nm=(l+r)*0.5*a+b; int mid=l+r+1>>1;
			if (nl <= p[w].pl && nr <= p[w].pr) return;
			if (nm > p[w].pm) {
				if (nl < p[w].pl || nr < p[w].pr) {
					if (nl < p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, p[w].a, p[w].b);
					if (nr < p[w].pr && l < r) insert(p[w].ch[1], mid, r, p[w].a, p[w].b);
				} p[w].a = a; p[w].b = b; p[w].pl = nl; p[w].pr = nr; p[w].pm = nm;
			} else {
				if (nl > p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, a, b);
				if (nr > p[w].pr && l < r) insert(p[w].ch[1], mid, r, a, b);
			}
 		}
		void query(int w, int l, int r, int pos) {
			if (!w) return;
			if (p[w].a) AnsTmp = max(AnsTmp, (LL)p[w].a * pos + p[w].b);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (pos < mid) query(p[w].ch[0], l, mid-1, pos);
				else query(p[w].ch[1], mid, r, pos);
			}
		}
}SGT;

int main() {
	n = read(); ATK = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		b = ceil((double)b / ATK) + EPS;
		r[i].v = a; r[i].t = b;
	}
	sort(r+1, r+1+n, cmp);
	for (int i=1;i<=n;i++) pre[i] = pre[i-1] + r[i].t;
	for (int i=n;i;i--) sum[i] = sum[i+1] + r[i].v;
	for (int i=1;i<=n;i++) {
		LL tmp = SGT.query(r[i].v);
		LL nv = sum[i]*r[i].t-r[i].v+pre[i-1]*r[i].v; 
		if (i > 1) vout = max(vout, tmp + nv);
		SGT.insert(-r[i].t, nv);
	}
	for (int i=1;i<=n;i++) ans += (pre[i] - 1) * r[i].v; 
	printf("%lld\n",ans-vout);
	return 0;
}