Codeforces #559 Div1 A. The Party and Sweets

CもDも比較的簡単だった回。
https://codeforces.com/contest/1158/problem/A

問題

N人の少年が、M人の少女にそれぞれいくつか飴をあげた。
その際、各少年iがあげた飴の最小値はA[i]であり、少女jが受け取った飴の最大値はB[j]である。

そのような飴のあげ方は達成可能か。可能なら総数の最小値を求めよ。

解法

A,Bを先にソートしておこう。

• Aの最大値がBの最小値より大きい場合、解なし。
• Aの最大値とBの最小値が等しい場合
  • 飴を一番少なくもらう少女は、少年全員から最小値をもらえばよい。これで少年側の条件は達成できる。
  • あの少女は、基本的に少年全員から最小値をもらうのだが、最大値に関する条件を満たすため、誰かひとりから大目に飴をもらわなければいけない。当然、Aが最大値の少年にその差分を出してもらおう。
• Aの最大値がBの最小値より大きい場合
  • 基本的には上のアプローチと同じだが、これだとAが最大値の少年が、入力の最小値を満たすタイミングがない。
  • よって、Bが最小の少女のみ、Aが2番目に大きい少年から差分を補填してもらおう。ただしN,Mが1の場合は解なし。

int N,M;
ll A[101010],B[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll sum=0;
	FOR(i,N) cin>>A[i], sum+=A[i];
	FOR(i,M) cin>>B[i];
	sort(A,A+N);
	sort(B,B+M);
	if(A[N-1]>B[0]) return _P("-1\n");
	
	ll ret=0;
	int ok=0;
	FOR(i,M) if(B[i]==A[N-1]) ok=1;
	if(ok==1) {
		FOR(i,M) ret+=sum+(B[i]-A[N-1]);
	}
	else {
		if(M==1||N==1) return _P("-1\n");
		FOR(i,M) {
			if(i==0) ret+=sum+(B[i]-A[N-2]);
			else ret+=sum+(B[i]-A[N-1]);
		}
	}
	cout<<ret<<endl;
	
}

まとめ

コーナーケースとか地味に面倒な問題。