Problem——C. Prefix Sum Primes——Codeforces

time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output We’re giving away nice huge bags containing number tiles! A bag we want to present to you contains n tiles. Each of them has a single number written on it — either 1 or 2.
However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.
Can you win the prize? Hurry up, the bags are waiting!
Input
The first line of the input contains a single integer n (1≤n≤200000) — the number of number tiles in the bag. The following line contains n space-separated integers a1,a2,…,an (ai∈{1,2}) — the values written on the tiles.
Output
Output a permutation b1,b2,…,bn of the input sequence (a1,a2,…,an) maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.
Examples
input

5
1 2 1 2 1

output

1 1 1 2 2

input

9
1 1 2 1 1 1 2 1 1

output

1 1 1 2 1 1 1 2 1

Note
The first solution produces the prefix sums 1,2,3,5,7 (four primes constructed), while the prefix sums in the second solution are 1,2,3,5,6,7,8,10,11 (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.
아이디어:
2가 먼저 2를 출력하고 2가 없으면 1부터 추가한다. 폭력 해결은 소수만 있으면 1이나 2를 출력한다. 추가하면서 출력하는 것이 아니다.
코드:

#include
#include 
#include
#include
#include
#include
#include
#include
#define ll long long
#define dd double
#define mes(x,y) memset(x,y,sizeof(y))
using namespace std;
int k(int x){
	int flag=1;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			flag=0;
		}
	}
	return flag;
} 
int main(){
	int n;
	cin>>n;
		int a=0,b=0,x;
		for(int i=0;i<n;i++){
			cin>>x;
			if(x==2){
				a++;
			}
			if(x==1){
				b++;
			}
		}
		n+=a;
		int sum=0;// 2   2， 2  1   
		while(sum!=n){
			if(k(sum+2)==1&&a!=0){
				cout<<"2 ";sum+=2;a--;
			}
			else if(k(sum+1)==1&&b!=0){
				cout<<"1 ";sum++;b--;
			}
			else{
				if(a!=0){
					sum+=2;a--;
					cout<<"2 ";
				}
				else if(b!=0){
					sum++;b--;
					cout<<"1 ";
				}
			}
		}//    ，        1 2，       。
		cout<<endl;
}