kmjp's blog

競技プログラミング参加記です

Codeforces #303 Div2 D. Queue

今回の問題でも特に簡単な謎問題。
http://codeforces.com/contest/545/problem/D

問題

N人の人がサービスを受けるために並んでいる。
各人は、自分がサービスを受けるのにかかる時間T[i]がわかっている。

人々は1列に並び、1人ずつサービスを受ける。
各人は、自分のサービスを受ける前の待ち時間がサービス時間を超えると怒って帰ってしまう。
人の並び順を変えられるとき、最大何人サービスを受けられるか。

解法

Tを昇順に並べ、順にサービスを受けられるか判定するだけ。

int N;
ll T[101000];
ll tot;
int ret;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i];
	sort(T,T+N);
	
	FOR(i,N) if(tot<=T[i]) ret++, tot+=T[i];
	cout<<ret<<endl;
	
}

まとめ

なんでこれDなんだろう。