| Memory Limit: 131072KB | 64bit IO Format: %lld & %llu |
Description
机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3...N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。
Input
第一行两个整数，N,S。
接下来N行每行两个整数，Ti,Fi。
Output
一个整数，为所求的答案。
Sample Input
5 1
1 3
3 2
4 3
2 3
1 4
Sample Output
153
Hint
Source
SDOI2012
BZOJ挂了，目前只过了样例，没有测试。
是 http://www.cnblogs.com/SilverNebula/p/5926270.html 这道题的强化版本，数据范围达到了1e6，同时t可能出现负值（强行时间倒流），这使得原本的公式不能保证斜率单调。
解决办法是不弹队头，保留所有位置，每次二分查找斜率最大位置。
——然而神tm我不管写什么算法，加上二分就WA，这次只是加个二分，又调了20分钟才过样例。
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
using namespace std;
const int mxn=1e6+;
long long read(){
long long x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
LL n;
LL s;
LL t[mxn],f[mxn];
LL sumt[mxn],sumf[mxn];
LL dp[mxn];
int q[mxn];
LL gup(int j,int k){
return (dp[j]-dp[k]);
}
LL gdown(int j,int k){
return sumf[j]-sumf[k];
}
LL gdp(int i,int j){
return dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]);
}
int main(){
n=read();s=read();
int i,j;
for(i=;i<=n;i++){
t[i]=read();f[i]=read();
sumt[i]=sumt[i-]+t[i];
sumf[i]=sumf[i-]+f[i];
}
memset(dp,0x3f,sizeof dp);
dp[]=;
int hd=,tl=;
q[hd]=;
for(i=;i<=n;i++){
int l=,r=tl;
while(l<r){
int mid=(l+r)>>;
if( ((double)dp[q[mid+]]-dp[q[mid]])>=(double)(s+sumt[i])*(sumf[q[mid+]]-sumf[q[mid]]))r=mid;
else l=mid+;
}
dp[i]=min(dp[i],gdp(i,q[l]));
printf("i:%d %lld\n",i,gup(i,q[l])/gdown(i,q[l]));
while(hd<tl && gup(i,q[tl])*gdown(q[tl],q[tl-])<=gup(q[tl],q[tl-])*gdown(i,q[tl]) )tl--;
q[++tl]=i;
}
printf("%lld",dp[n]);
return ;
}