首页 > 代码库 > 【模拟】NCPC 2014 E ceremony
【模拟】NCPC 2014 E ceremony
题目链接:
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1791
题目大意:
N栋大楼(N<=100000),拆除的时候有两种选择的操作,可以拆掉一整栋,或者把当前所有大楼的第x层拆掉(高度小于x的没用),并且x以上的所有楼层高度-1.(相当于所有高于x的大楼抽掉一层)
问把N栋大楼拆掉至少要几次拆除操作。
题目思路:
【模拟】
先将大楼高度排序,之后考虑分界线,枚举I,I之后的大楼都是被单个拆除,而I和I之前的大楼都是被一层一层拆除。ans=min(n-i+h[i])
1 // 2 //by coolxxx 3 //#include<bits/stdc++.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<iomanip> 8 #include<map> 9 #include<stack>10 #include<queue>11 #include<set>12 #include<bitset>13 #include<memory.h>14 #include<time.h>15 #include<stdio.h>16 #include<stdlib.h>17 #include<string.h>18 //#include<stdbool.h>19 #include<math.h>20 #define min(a,b) ((a)<(b)?(a):(b))21 #define max(a,b) ((a)>(b)?(a):(b))22 #define abs(a) ((a)>0?(a):(-(a)))23 #define lowbit(a) (a&(-a))24 #define sqr(a) ((a)*(a))25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))26 #define mem(a,b) memset(a,b,sizeof(a))27 #define eps (1e-8)28 #define J 1029 #define mod 100000000730 #define MAX 0x7f7f7f7f31 #define PI 3.1415926535897932332 #define N 10000433 using namespace std;34 typedef long long LL;35 int cas,cass;36 int n,m,lll,ans;37 int h[N];38 bool cmp(int a,int b)39 {40 return a<b;41 }42 int main()43 {44 #ifndef ONLINE_JUDGE45 // freopen("1.txt","r",stdin);46 // freopen("2.txt","w",stdout);47 #endif48 int i,j,k;49 // for(scanf("%d",&cass);cass;cass--)50 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++)51 // while(~scanf("%s",s+1))52 while(~scanf("%d",&n))53 {54 for(i=1;i<=n;i++)55 scanf("%d",&h[i]);56 sort(h+1,h+1+n,cmp);57 ans=min(n,h[n]);58 for(i=1;i<n;i++)59 ans=min(ans,n-i+h[i]);60 printf("%d\n",ans);61 }62 return 0;63 }64 /*65 //66 67 //68 */
【模拟】NCPC 2014 E ceremony
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。