SCNU 2015ACM新生赛初赛【1006. 3D打印】解题报告
2024-08-26 17:38:10
题目链接详见SCNU 2015新生网络赛 1006. 3D打印 。出题思路来自codevs 3288. 积木大赛,属于模拟题。
首先我们把“选择从第L部分到第R部分”理解为“选择一段连续的部分”,OK,基本题意为:给定N个部件的高度,每次可以给连续的一段增加高度$1$,问至少需要几次增加高度的操作?
不少人认为,直接模拟这个操作,循环给它$+1$,数加几次能达到要求高度就可以了。但很可惜这是会超时TLE哒。我们考虑极端情况,总共有$10^{5}$个部分,高度$h_{i}$是$0$和$10^{5}$相间的,这样总共需要$\frac {10^{5}} {2} \times 10^{5} = 5 \times 10^{9}$次操作,复杂度为$O(NH)$,也就是说很可能一些同学的做法,会要进行$5 \times 10^{9}$次的循环,运行结果同样也是$5 \times 10^{9}$,不但超时,而且还超了$int$整型的范围。当然良心出题人并没有把这组数据放进去,数据做了奇怪的限定能保证结果不超过$int$,否则你应该需要拿long long或__int64来存放结果(32位机下$int$和$long$都是$4$字节,一样的范围)。
那怎么办呢?我们可以发现,如果$h_{i} > h_{i-1}$,那么总操作次数应要加上$h_{i} - h_{i-1}$,因为假定我在到达前面高度为$h_{i-1}$的部分的时候,已经总共操作了$t_{1}$次,如果当前部分比前面的还高,那么这个部分的下面$h_{i-1}$的高度已经被前面的操作完成了(尽量选择连续的一段增加高度),于是这里我只剩下了$t_{2} = h_{i} - h_{i-1}$的高度未完成。如果$h_{i} \leq h_{i-1}$,则前面的操作肯定也把这部分顺便完成了,因此不需要再次计算。由于每次只需要比较$h_{i}$和$h_{i-1}$的大小关系,前面比较过的与后面的无关,所以只需要一个循环把数组遍历一次就可以了,复杂度为$O(N)$。
代码如下(我是在读入的时候就完成判断,因此不需要数组保存了):
#include <stdio.h> int main() {
int T, N;
scanf("%d", &T);
while(T--) {
int t = , x;
long long res = ;
scanf("%d", &N);
for(int i=; i<N; i++) {
scanf("%d", &x);
if(x>t) res += x-t;
t = x;
}
printf("%I64d\n", res);
}
return ;
}
在提交的代码中发现有同学想到了另一种方法,即寻找极大极小值的做法,复杂度同样为$O(N)$。比如我先找到一个极小值$rmin$,往后面找到一个极大值$rmax$,这样总次数只需加上$rmax - rmin$即可,因为极小值前面的部分已经计算过了,只需要考虑极小值到极大值之间的操作次数就好了。当然一开始时极小值为$0$,遍历结束后也要注意加上还没计算的部分,略微麻烦点,留给大家思考。
附:数据生成程序如下:
#include <stdio.h>
#include <random>
using namespace std;
default_random_engine g1;
default_random_engine g2;
lognormal_distribution<double> lognDis(, );
uniform_int_distribution<int> uiDis(, 1E5); int main() {
freopen("in.txt", "w+", stdout);
int T = ;
printf("%d\n", T);
while(T--) {
int N = lognDis(g1);
if(N>1E5) N%=int(1E5);
printf("%d\n", N);
for(int i=; i<N; i++) {
int Hi = uiDis(g2);
printf("%d ", Hi);
}
puts("");
}
return ;
}
Click To
——by BlackStorm, from here: http://www.cnblogs.com/BlackStorm/p/4988115.html .
最新文章
- 读书笔记--SQL必知必会13--创建高级联结
- 从service弹出系统级自定义提示框,可在任意页面弹出
- [Linux] 关于Centos6中ulimit nproc用户进程数的限制
- sasscore22
- Java 菜鸟学习之 script脚本语句
- python字符串格式化方法 format函数的使用
- windows路径操作API函数
- LeetCode之Min Stack 实现最小栈
- Oracle11g创建表空间语句
- PHP基础语法2
- memcached原理全面剖析
- 为什么报错说req未定义,createServer只接受匿名函数吗?
- [HMLY]2.CocoaPods详解----进阶
- Java 反射 Array动态创建数组
- CSharp笔记>;>;>;多语言,注册
- MySql中三种注释写法
- python 分片、截断序列
- 部分手机(如三星)的Listview列表会自动加上黑线解决办法
- json化的必要性
- HDUOJ----2159 FATE
热门文章
- ASP.NET中Session的sessionState 4种mode模式
- ASP.NET MVC5+EF6+EasyUI 后台管理系统(40)-精准在线人数统计实现-【过滤器+Cache】
- C#:浅析结构与类的区别
- 设计模式(七): 通过转接头来观察";适配器模式";(Adapter Pattern)
- Android GPS应用开发
- 修改版: 小伙,多线程(GCD)看我就够了,骗你没好处!
- Win10桌面预览版14316更新内容大全
- 使用Beautiful Soup编写一个爬虫 系列随笔汇总
- 用Crontab打造简易工作流引擎
- Linux用户体系和文件权限总结