原題
A. Doremy's Paint 3
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
An array?𝑏1,𝑏2,…,𝑏𝑛�1,�2,…,��?of positive integers is good if all the sums of two adjacent elements are equal to the same value. More formally, the array is good if there exists a?𝑘�?such that?𝑏1+𝑏2=𝑏2+𝑏3=…=𝑏𝑛?1+𝑏𝑛=𝑘�1+�2=�2+�3=…=��?1+��=�.
Doremy has an array?𝑎�?of length?𝑛�. Now Doremy can permute its elements (change their order) however she wants. Determine if she can make the array good.
Input
The input consists of multiple test cases. The first line contains a single integer?𝑡�?(1≤𝑡≤1001≤�≤100)?— the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer?𝑛�?(2≤𝑛≤1002≤�≤100)?— the length of the array?𝑎�.
The second line of each test case contains?𝑛�?integers?𝑎1,𝑎2,…,𝑎𝑛�1,�2,…,��?(1≤𝑎𝑖≤1051≤��≤105).
There are no constraints on the sum of?𝑛�?over all test cases.
Output
For each test case, print "Yes" (without quotes), if it is possible to make the array good, and "No" (without quotes) otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
Example
input
Copy
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000
output
Copy
Yes Yes No No Yes
Note
In the first test case,?[8,9][8,9]?and?[9,8][9,8]?are good.
In the second test case,?[1,2,1][1,2,1]?is good because?𝑎1+𝑎2=𝑎2+𝑎3=3�1+�2=�2+�3=3.
In the third test case, it can be shown that no permutation is good.
鏈接
傳送門
代碼
#include<bits/stdc++.h>
using namespace std;int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);map<int,int> occ;for(int i=0;i<n;i++){int x;scanf("%d",&x);occ[x]++;}if(occ.size()>=3) puts("No");else{if(abs(occ.begin()->second-occ.rbegin()->second)<=1)puts("Yes");elseputs("No");}}return 0;
}總結
1.題目的意思是，輸入一個數列，詢問，能否經過若干次交換順序，使得，該數列變成這樣的數列：任意兩個相鄰的元素之和相等
2.如果要滿足任意兩個相鄰元素之和相等，可以這樣來考慮，
a1+a2=a2+a3
a2+a3=a3+a4
a3+a4=a4+a5
a4+a5=a5+a6
觀察上面的式子，可以發現，a1=a3=a5
?a2=a4=a6
也就是說經過改變順序之后，數列元素間隔一項，兩個元素相等，假設有偶數個元素，就意味著下標是奇數的元素都相等，下標是偶數的元素都相等
如果有奇數個元素，12121，比如說有5個元素，如果仍然滿足間隔一項相等，還是可以滿足要求
偶數：n/2個奇數下標，n/2個偶數下標
奇數：n/2個奇數下標,n-n/2個偶數下標（注意這里的除法是向下取整的除法）
或者 n/2個偶數下標，n-n/2個奇數下標（除法是向下取整的）
3.如果有3個不同的元素，無論如何不可以滿足要求，比如說1，2，3，任意兩個相鄰元素之和都不會相等，無法滿足要求
4.可以記錄某一個數字出現的次數，比較這兩個數字出現的次數，從而判斷能否經過修改，使得滿足題目要求。如果兩個數字出現次數相同，表示是1212這種情況，如果兩個數字出現次數之差等于1，表示12121這種情況
5.另外的情況不滿足題目要求
6.map可以存兩個數據，第一個數據也就是所謂的key，存的是數值，第二個數據存的是該數值出現的次數，和pair差不多，都是存兩個數據
7.map.size()表示map里面有多少個元素，也就是說在這個數列里面有多少個不同的數字
8.map.begin()表示起始元素，map.begin()->second表示起始元素存的數值，也就是某數字出現的次數，map.rbegin()表示map的最后一個元素
9.pair用.second，map用->second（大概是這樣，以后發現不對的話再來修改）
