Codeforces Round #672 (Div. 2) 1420A 【思维】题解

亦凉 2021-07-24 17:49 331阅读 0赞

### 前言 ###

> 欢迎大家访问林深时不见鹿的博客，本博客致力于最通俗易懂的题解，如有不足， 还请多多指教。

### 目录 ###

*   *   *  前言
         *  1.题意
         *  2.思路
         *  3.代码

**CodeForces - 1420A**  
For god’s sake, you’re boxes with legs! It is literally your only purpose! Walking onto buttons! How can you not do the one thing you were designed for?  
Oh, that’s funny, is it? Oh it’s funny? Because we’ve been at this for twelve hours and you haven’t solved it either, so I don’t know why you’re laughing. You’ve got one hour! Solve it!

Wheatley decided to try to make a test chamber. He made a nice test chamber, but there was only one detail absent — cubes.

For completing the chamber Wheatley needs n cubes. i-th cube has a volume ai.

Wheatley has to place cubes in such a way that they would be sorted in a non-decreasing order by their volume. Formally, for each i>1, ai−1≤ai must hold.

To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any i>1 you can exchange cubes on positions i−1 and i.

But there is a problem: Wheatley is very impatient. If Wheatley needs more than n⋅(n−1)2−1 exchange operations, he won’t do this boring work.

Wheatly wants to know: can cubes be sorted under this conditions?

Input  
Each test contains multiple test cases.

The first line contains one positive integer t (1≤t≤1000), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer n (2≤n≤5⋅104) — number of cubes.

The second line contains n positive integers ai (1≤ai≤109) — volumes of cubes.

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output  
For each test case, print a word in a single line: “YES” (without quotation marks) if the cubes can be sorted and “NO” (without quotation marks) otherwise.

Example  
Input

3
    5
    5 3 2 1 4
    6
    2 2 2 2 2 2
    2
    2 1

Output

YES
    YES
    NO

Note  
In the first test case it is possible to sort all the cubes in 7 exchanges.

In the second test case the cubes are already sorted.

In the third test case we can make 0 exchanges, but the cubes are not sorted yet, so the answer is “NO”.

### 1.题意 ###

给你一个数组，你可以每次交换相邻两个数，使得该数组单调不下降，如果你交换的次数超过 n\*(n-1)/2 -1 输出YES，否则输出 NO。

### 2.思路 ###

这道题就是求解冒泡排序交换的次数，但你如果直接用冒泡排序去求解的话，一个样例的时间复杂度是O(n),1000个样例肯定会超时的。当一个数组严格单调下降时，即冒泡排序最坏的情况下交换次数为 n-1+n-2+n-3+…+ 2+1 即n\*(n-1)/2 ,我们可以发现和题目要求的次数n\*(n-1)/2 -1正好差一。因此只要数组不是严格单调下降数组都可以满足要求。

### 3.代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N = 5e4 + 10;
    int a[N];
    int main()
    { 
    	int T;
    	cin >> T;
    	while (T--)
    	{ 
    		int n;
    		cin >> n;
    		for (int i = 0; i < n; i++) cin >> a[i];
    		int flag = 1;
    		for (int i = 0; i < (n-1); i++)
    		{ 
    			if (a[i] <= a[i + 1]) 
    			{ 
    				flag = 0;
    				break;
    			}
    		}
    		if(flag==0) puts("YES");
    		else puts("NO");
    	}
    	return 0;
    }