紫书 习题 8-24 UVa 10366 (构造法)
2024-08-31 12:21:05
又是一道非常复杂的构造法……
#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 1123;
int L, R, LHs[MAXN], RHs[MAXN], LH, RH, LHi, RHi;
int solve()
{
int lt = 0, rt = 0, t;
for(int i = L, h = LHs[L]; i > LHi; i--) //从最高隔板到边缘的时间
lt += h, h = max(h, LHs[i-1]);
for(int i = R, h = RHs[R]; i > RHi; i--)
rt += h, h = max(h, RHs[i-1]);
if(LH == RH) return (LHi + RHi + 1) * LH + min(lt, rt) * 2; //小细节, 矩形宽要加1, 拿样例算一下就知道了
int T = min(LH, RH), LTi = 0, RTi = 0;
while(LTi < L && LHs[LTi] < T) LTi++;
while(RTi < R && RHs[RTi] < T) RTi++;
if(LH < RH)
{
rt = 0;
for(int i = RTi, h = T; RHs[i] <= T; i++)
rt += h, h = max(RHs[i+1], h);
t = lt > rt ? (lt + rt) : 2 * lt;
}
if(LH > RH)
{
lt = 0;
for(int i = LTi, h = T; LHs[i] <= T; i++)
lt += h, h = max(LHs[i+1], h);
t = rt > lt ? (lt + rt) : 2 * rt;
}
return t + (RTi + LTi + 1) * T;
}
int main()
{
int lx, rx;
while(scanf("%d%d", &lx, &rx) && lx && rx)
{
LH = RH = 0;
L = (-lx) / 2, R = rx / 2;
for(int i = lx; i < 0; i += 2)
{
int j = (-i) / 2; scanf("%d", &LHs[j]);
if(LH <= LHs[j]) LH = LHs[j], LHi = j;
}
for(int i = 1; i <= rx; i += 2)
{
int j = i / 2; scanf("%d", &RHs[j]);
if(RH < RHs[j]) RH = RHs[j], RHi = j;
}
printf("%d\n", solve() * 2); //开始除以2, 后来乘回去
}
return 0;
}
最新文章
- Linux From Scratch - Version 7.7-systemd (中文)
- demo工程的清单文件及activity中api代码简单示例
- Sql [hierarchyid]类型如何动态插入层级数据
- Hibernate 缓存机制
- POJ3009 Curling 2.0
- 【HDOJ】3285 Convex Hull of Lattice Points
- PHP 中 AJAX 中文乱码解决
- [Swust OJ 191]--迷宫逃离(打表搜索)
- SSIS中Sql Task 获取系统变量
- 基于IDL 的WebRS系统设计图
- 1630/2023: [Usaco2005 Nov]Ant Counting 数蚂蚁
- Drrols规则引擎
- Android--SoundPool
- Eclipse中代码字体背景变红/变黄/变绿
- Java中十六进制转换 Integer.toHexString()
- mysql的group by查询
- makefile 双冒号规则
- Linux可重入函数和线程安全的区别与联系(转)
- linux文件和目录的删除、新建、移动等操作
- node.js中对Event Loop事件循环的理解
热门文章
- laravel :Call to undefined function App\Http\Controllers\success() 解决方法
- HDU 5918 Sequence I
- s5k4ba摄像头驱动分析
- UVA 11404 Palindromic Subsequence
- Java 学习(10):java 异常处理
- webserver的作用!
- nginx源代码分析--从源代码看nginx框架总结
- Qt 3D教程(三)实现对模型材质參数的控制
- 【笨木头Lua专栏】基础补充02:函数的几个特别之处
- m-orchastration system