首页 > 代码库 > 【模拟】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 */
View Code

 

【模拟】NCPC 2014 E ceremony