Geometry Dash [yukicoder 322] - はまやんはまやんはまやん

問題

N個のステージがある。
i番目のステージには、通過時間T[i]、難易度D[i]が決められている。
ステージを入れ替えたときの終了までの通過時間を以下のように求める。

1. 並び替えた順にステージを訪れるとする
2. 最初は1番目からはじめて、順番にステージを訪れていく
3. 各ステージを訪れた回数をカウントしておき、訪れた回数が難易度以下であれば、T[i]/2経過後に最初のステージに戻る
4. 各ステージを訪れるときは毎回T[i]かかるものとして、全てのステージを巡り終えたら終了

終了までの経過時間が最大になるときのステージの順番を求めよ。

2 <= N <= 10^5
1 <= Ti <= 10^4
1 <= Di <= 10^4

考察

1. この問題の特徴は「最大の時のステージの順番を出力する」という部分
2. こういう系統は以下の方法しかないかなと思ってる

DPなどを作り、そこから逆算する
ソーティングを工夫する

3. 今回は、計算量もO(nlogn)想定っぽいのでソーティングで解くのでは？
4. ステージaとステージbがあった時に、
T[a]*D[b] > T[b]*D[a]
であれば、終了までの経過時間がより増える
5. これを比較関数としてソートする

6. （比較関数はTとDを使うだろうなと思って、あまり考えずに作って通ったやつで通しました）
7. （数学的な証明はできないです）

実装

http://yukicoder.me/submissions/102681

int N;
int T[101010], D[101010];
//-----------------------------------------------------------------
int ans[101010];
bool comp(int a, int b)
{
	return T[a] * D[b] > T[b] * D[a];
}
//-----------------------------------------------------------------
int main()
{
	scanf("%d", &N);
	rep(i, 0, N) scanf("%d", &T[i]);
	rep(i, 0, N) scanf("%d", &D[i]);

	rep(i, 0, N) ans[i] = i;
	sort(ans, ans + N, comp);

	rep(i, 0, N) printf("%d ", ans[i] + 1);
	printf("\n");
}