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