Treasurecave

NC214492. Treasurecave

描述

Xiao Qian really likes money. One day, He saw many coins in a cave. He immediately ran in. The bad thing is that the front door of the cave closed suddenly. Fortunately there was a paper in the cave that said

"Welcome to Treasure cave! As you can see, there are n piles of coins in the air and a pile of coins on the ground. The ith pile on the air has a_icoins. The pile on the ground has x coins. Now, there is a magic that you can choose a pile on the air and swap the pile with the ground pile. You can use this magic any times. The back door opens when the piles of coins on the air are strictly increased(it is considered strictly increased when a₁<a₂<a₃<...<a_n holds). You can take the ground pile out when the back door is open. Good Luck!"

Now you task is whether can Xian Qian get out of the cave. If he can, what is the maximum coins can Xiao Qian take out, else just output 0.

输入描述

The first line contains one integer t(1<=t<=20)——the number of test cases.
Each test case consists of two lines.
The first line contains two integers n and x(1<=n<=10⁵,1<=x<=10⁹)——the number of piles on the air and the numer of coins on the ground. 
The second line contains n integers a₁, a₂, a₃, ... , a_n(1<=a_i<=10⁹)_.

输出描述

For each test case, print one line consists of one integer.

示例1

输入:

输出:

5
0

说明:

In the first test case.

At first swap x and a₃. Then x=2, a={1,5,4}.

Second swap x and a₂. Then x=5,a={1,2,4}.

So the answer is 5.

In the second test case, Xiao Qian can not get out in any way.

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 172ms, 内存消耗: 4584K, 提交时间: 2021-01-27 09:52:19

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];

int main(){
	int n;
	cin>>n;
	while(n--){
		int n,x;
		int numn;
		int num=0;
		cin>>n>>x;
		for(int i=0;i<n;i++) cin>>a[i];
		a[n]=x;
		sort(a,a+1+n);
		for(int i=0;i<=n;i++){
			if(a[i]==a[i-1]) {
			num++;
			numn=a[i];
			}
		} 	
		if(num>1) cout<<"0"<<endl;
		else if(num==1) cout<<numn<<endl;
		else cout<<a[n]<<endl;
	} 
	
}

Python3 解法, 执行用时: 201ms, 内存消耗: 22552K, 提交时间: 2021-12-24 12:24:33

T=eval(input())
for i in range(T):
    m=input().split()
    x=eval(m[0])
    n=eval(m[1])
    a=[]
    m=input().split()
    for i in range(x):
        a.append(int(m[i]))
    a.append(n)
    if len(set(a))==len(a):
        print(max(a))
    elif len(set(a))==len(a)-1:
        for i in a:
            if a.count(i)==2:
                print(i)
                break
    else:
        print(0)

上一题

下一题

详情