torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #179, Division 2, A : Yaroslav and Permutations

概要

N 項からなる数列が与えられる。
隣り合う二要素を交換する操作ができるとき、全ての隣り合う要素が異なるようにできるか判定せよ。

解法

許可された操作だけで、任意の形に変形することができます。
従って、等しい要素の数だけで判定することが可能です。
( 一番多い要素の数 ) / 2 (端数切り上げ)が n / 2 を超えるかどうかで判定できます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int count = 0;
	REP( i, 0, n )
	{
		count = max( count, std::count( ALL( as ), as[i] ) );
	}

	cout << ( count <= n / 2 + ( n % 2 ) ? "YES" : "NO" ) << endl;

	return 0;
}