3月14日第三題！！！（雖然是15號發的qwq）
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
補：范圍：
1<=N<=3*10^5,0<=s,ci<=512,-512<=ti<=512.
數據較小版本（n^2即可）請點這：http://blog.csdn.net/ye_xingyu/article/details/79562237
斜率優化，斜率為（s+sumT[i]），當截距最小時的f[i]就是當前最優決策
注意：ti有負數，則sumT[i]不具有單調性要把隊列中全部存著（隊尾仍可去掉無用決策即不滿足下凸性）用二分每次找到左側斜率小于當前斜率右側大于的位置，直接用方程轉移（即不用min）
code：
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int MAX=300010;
const int INF=0x3f3f3f3f;
int n,s,l,r;
long long ti[MAX],fi[MAX],f[MAX],q[MAX];
//注意開long long 前綴和還是很大的，我因為這個wa兩次QAQint search(int k) {if(l==r) return q[l];int L=l,R=r;while(L<R) {int mid=(L+R)>>1;if(f[q[mid+1]]-f[q[mid]]<=k*(fi[q[mid+1]]-fi[q[mid]])) L=mid+1;else R=mid;}return q[L];
}int main() {scanf("%d %d",&n,&s);for(int i=1;i<=n;i++) {scanf("%lld %lld",&ti[i],&fi[i]);ti[i]+=ti[i-1];fi[i]+=fi[i-1];}r=l=1;for(int i=1;i<=n;i++) {int p=search(s+ti[i]);f[i]=f[p]-(s+ti[i])*fi[p]+ti[i]*fi[i]+s*fi[n];while(l<r && (f[q[r]]-f[q[r-1]])*(fi[i]-fi[q[r]])>=(f[i]-f[q[r]])*(fi[q[r]]-fi[q[r-1]])) r--;q[++r]=i;}printf("%lld",f[n]);return 0;
}通過這個題重新復（zi）習(xue)了下斜率優化感覺斜率優化就是來一個維護比值單調的隊列（這個值就對應線性規劃的坐標系中的斜率）從中選出最優決策。（不過感覺弄方程變形又弄變量有點麻煩233~）
期待之后有關斜率優化的繼續學習與練習(￣▽￣)／。
