JOI春合宿 2011-day4 IOI
問題文 : 国際情報オリンピック
解法 :
まず,
"G を,N 問の合計点が G 点以上の選手の人数が全体の 1 / 12 以上となるような最大の値とする.このとき,金メダルが与えられる条件は,N 問の合計点が G 点以上であることである."
ということを, 問題を解きやすくするために言い換える. これは,
"最終日での順位が [全体の人数 / 12] の小数点を切り上げた順位よりも高い"
といいかえられる.
そこで, ある人の最終日での順位の最大値と最小値を考えれば良い. これは, 予め, 全員の最大得点と最小得点を考えてソートしておくと, 二分探索で効率良く求めることが出来る.計算量はO(k log k)である.
コード :
#include <cstdio> #include <algorithm> #define MAX_K (100000) using namespace std; int scoreMin[MAX_K], scoreMax[MAX_K]; int datMin[MAX_K], datMax[MAX_K]; int state[MAX_K]; int main() { int k, n, m; scanf("%d %d %d", &k, &n, &m); for (int i = 0; i < k; i++){ scanf("%d", scoreMin + i); scoreMax[i] = scoreMin[i] + (n - m) * 100; datMin[i] = scoreMin[i]; datMax[i] = scoreMax[i]; } sort(datMin, datMin + k); sort(datMax, datMax + k); for (int i = 0; i < k; i++){ int rankUp = k + 1 - (upper_bound(datMin, datMin + k, scoreMax[i]) - datMin); int rankDown = k + (n == m) - (upper_bound(datMax, datMax + k, scoreMin[i]) - datMax); state[i] = (rankUp <= (k + 11) / 12) + (rankDown <= (k + 11) / 12); } for (int i = 0; i < k; i++){ if (state[i] > 1) printf("%d\n", i + 1); } printf("--------\n"); for (int i = 0; i < k; i++){ if (state[i]) printf("%d\n", i + 1); } return (0); }