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