首页 > 代码库 > Noip 2013 Day2 T1 积木大赛(block)
Noip 2013 Day2 T1 积木大赛(block)
Noip 2013 Day2 T1 积木大赛(block)
【题目描述】
春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为的大厦,大厦可以看成由块宽度为1的积木组成,第??块积木的最终高度需要是??? 。
在搭建开始之前,没有任何积木(可以看成块高度为 0 的积木)。接下来每次操作,小朋友们可以选择一段连续区间[, ??],然后将第块到第??块之间(含第 L 块和第 R 块)所有积木的高度分别增加1。
小M是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。
【输入】
输入文件为 block.in
输入包含两行,第一行包含一个整数,表示大厦的宽度。
第二行包含个整数,第??个整数为?
?? 。
【输出】
输出文件为 block.out
仅一行,即建造所需的最少操作数。
这道题并没有什么难度,只是我以为很难,题目中提到区间内增加一个值,我很自然的想到了什么线段树啊,树状数组,离线前缀和啊。果然,我又想多了。还好自己反应过来了。正解的话贪心就好了。
我们假设每一次搭建操作都是一条删除线,那么答案就是最少的删除线条数。
当hi<hi+1时,显然必须增加删除线,去补充多出来的hi+1−hi部分;
当hi>hi+1时,有些删除线就必须要终止,接下来只有hi+1条删除线可以存在。
于是只需要计算增加的删除线总数即可,时间复杂度为O(n)。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #define INT_MAX_ 0x7fffffff 7 #define LONG_MAX_ 0x7fffffffffffffffll 8 #define pi acos(-1) 9 #define N 10001010 #define M 101011 using namespace std;12 13 inline int read()14 {15 int data=http://www.mamicode.com/0,w=1;16 char ch=0;17 while(ch!=‘-‘ && (ch<‘0‘ || ch>‘9‘)) ch=getchar();18 if(ch==‘-‘) w=-1,ch=getchar();19 while(ch>=‘0‘ && ch<=‘9‘) data=http://www.mamicode.com/data*10+ch-‘0‘,ch=getchar();20 return data*w;21 }22 23 inline void write(int x)24 {25 if(x<0) putchar(‘-‘),x=-x;26 if(x>9) write(x/10);27 putchar(x%10+‘0‘);28 }29 30 int n;31 int pre_house,all_of_house,nowVal;32 33 int main()34 {35 freopen("block.in","r",stdin);36 freopen("block.out","w",stdout);37 38 n = read();39 for(int i = 1; i <= n; i++)40 {41 nowVal = read();42 if(pre_house < nowVal) all_of_house += nowVal - pre_house;43 pre_house = nowVal;44 }45 write(all_of_house);46 47 return 0;48 }
Noip 2013 Day2 T1 积木大赛(block)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。