[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=2726

[算法]

此题与POJ1180非常相似

但是 , 此题中的t值可能为负 , 这意味着不能每次都将斜率 <= k的点弹出 , 而需要在凸壳中进行二分查找

时间复杂度 : O(NlogN)

[代码]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + ;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n , S , l , r;
ll sumc[N] , sumt[N] , f[N];
int q[N] , c[N] , t[N]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline int _binary_search(int L , int R , int val)
{
int l = L , r = R , ret = L;
while (l <= r)
{
int mid = (l + r) >> ;
if (f[q[mid + ]] - f[q[mid]] <= val * (sumc[q[mid + ]] - sumc[q[mid]]))
{
ret = mid + ;
l = mid + ;
} else r = mid - ;
}
return ret;
} int main()
{ read(n); read(S);
for (int i = ; i <= n; i++)
{
read(t[i]);
read(c[i]);
sumt[i] = sumt[i - ] + t[i];
sumc[i] = sumc[i - ] + c[i];
}
f[q[l = r = ] = ] = ;
for (int i = ; i <= n; i++)
{
int pos = _binary_search(l , r - , S + sumt[i]);
f[i] = f[q[pos]] - sumc[q[pos]] * (S + sumt[i]) + sumt[i] * sumc[i] + S * sumc[n];
while (l < r && (f[i] - f[q[r]]) * (sumc[q[r]] - sumc[q[r - ]]) <= (f[q[r]] - f[q[r - ]]) * (sumc[i] - sumc[q[r]])) --r;
q[++r] = i;
}
printf("%lld\n" , f[n]); return ; }

最新文章

  1. MYSQL复制
  2. CC_STACKPROTECTOR防内核堆栈溢出补丁分析【转】
  3. Linux 视频设备驱动V4L2最常用的控制命令
  4. 插件开发--BE插件开发
  5. ios中属性和对象的初始化
  6. 《慕客网:IOS动画案例之会跳动的登入界面(上)》学习笔记 -Sketch的使用
  7. iOS CoreData 的级联删除等操作
  8. 浅析python的string.Template
  9. ios开发——实用技术总结Swift篇&amp;swift常用开发技术总结
  10. spring &lt;context:component-scan&gt;(转)
  11. PHP中的urlencode和urldecode的理解
  12. Linux网络基础配置
  13. List------Linked 链表
  14. Google Bigtable (中文版)
  15. [Swift]LeetCode308. 二维区域和检索 - 可变 $ Range Sum Query 2D - Mutable
  16. tomcat (选号)公司tomcat无页面解决
  17. Less or Equal CodeForces - 977C (sort+细节)
  18. 查询数据库中含clob,blob的表
  19. 12. The Biggest Safety Threat Facing Airlines 航空公司面临的最大安全威胁
  20. 分享url带中文参数,打开html操作完毕跳转jsp页面中文乱码解决

热门文章

  1. DELPHI的BPL使用
  2. iOS上如何让按钮(UIbutton)文本左对齐展示
  3. cucumber 使用资料
  4. 首先使用flex制作table
  5. 免费DNSserver有哪些?
  6. C/C++程序到内存分配(转)
  7. python(39)- 网络编程socket练习
  8. laravel 配置了自己的域名以后, localhost 无法访问 404 not found 的解决方法
  9. multimap容器和multiset容器中的find操作
  10. SegmentFault 巨献 1024 程序猿游戏「红岸的呼唤」第二天任务攻略