洛谷——P1897 电梯里的爱情（两种解法：普通方法、桶排序方法）

心已赠人 2023-10-02 12:58 96阅读 0赞

## P1897 电梯里的爱情 ##

### 题目背景 ###

木有……

### 题目描述 ###

细心的同事发现，小 W 最近喜欢乘电梯上上下下，究其原因，也许只有小W自己知道：在电梯里经常可以遇到他心中的女神 PR。

电梯其实是个很暧昧的地方，只有在电梯里，小 W 才有勇气如此近距离接近女神，虽然觉得有点不自在，但次数多了，女神也习惯了小 W 的存在，甚至熟悉到仿佛不说上句话自己也都觉得不合适了。可是，他们的谈话也仅仅限于今天天气不错啊或是你吃了吗之类的，往往在对方微笑点头后就再次陷入难堪的沉默之中。 于是，小 W 便在陪伴女神的同时，也关注着电梯中显示的楼层数字，并且他注意到电梯每向上运行一层需要 66 秒钟，向下运行一层需要 44 秒钟，每开门一次需要 55 秒（如果有人到达才开门），并且每下一个人需要加 11 秒。

特别指出，电梯最开始在 00 层，并且最后必须再回到 00 层才算一趟任务结束。假设在开始的时候已知电梯内的每个人要去的楼层，你能计算出完成本趟任务需要的总时间吗?

这是个很简单的问题，要知道，小 W 已经修炼到快速心算出结果的境界，现在你来编程试试吧！

### 输入格式 ###

共 22 行

第 11 行，一个正整数 n*n*，表示乘坐电梯的人数。

第 22 行，n*n* 个正整数，a\_\{i\}*a\*\*i* 表示第 i*i* 个人要去的楼层。

### 输出格式 ###

仅 11 行，一个正整数，表示完成这趟任务需要的时间。

### 输入输出样例 ###

**输入 \#1**复制

4
    2 4 3 2

**输出 \#1**复制

### 说明/提示 ###

对于 60%60% 的数据 0<n<10^40<*n*<104

对于 100%100% 的数据 0<n<10^50<*n*<105，0<a\_\{i\}\\leq 2\\times 10^70<*a\*\*i*≤2×107。

--------------------

解法一；

#include<bits/stdc++.h>
    #include<algorithm>
    using namespace std;
    long long m=1e5+5;
    int main(){
        
    
    	int n,a[m];
    	int sumTime;
    	cin>>n;
    	for(int i=0;i<n;i++){
        
    		cin>>a[i];
    	}
    	sort(a,a+n);
    	int shanglouTime=6*a[n-1];
    	int xialouTime=4*a[n-1];
    	int xiarengTime=n;
    	int s=unique(a,a+n)-a;//计算不重复楼层的数目 
    	int kaimengTime=0;
    	for(int i=0;i<s;i++){
        
    	 kaimengTime+=5;
    	}
    	 sumTime=shanglouTime+xialouTime+xiarengTime+kaimengTime;
    	cout<<sumTime;
    	
    	
    	return 0;
    }

--------------------

解法二：桶排序

#include <cstdio>
    int n,a,ans,max;//n是人数，a是这个人要去几层，ans是答案，max是最高楼层
    bool s[100000000];//楼层桶（不可思议的100000000层大楼）
    int main(void){
        
        s[0]=1;//注意！0层不需要开门！我一开始少了这句话丢了30分
        scanf ("%d",&n);//读n
        for (int i=0;i<n;i++){
        
            scanf ("%d",&a);//每次读一个人
            if (!s[a])ans+=5;//!s[a]意思是这个楼层还没见过，当然要开一次门啦
            s[a]=1;//不管怎样，标记一下
            if (a>max)max=a;//找最高楼层
        }
        ans+=n;//每个人都要下去，所以加的时间一定等于n
        ans+=max*10;//上6下4，共10s，所以最高楼层*10
        printf ("%d",ans);//输出！
    }