相关链接
题目传送门: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; }