롤러코스터

1. 롤러코스터 2. 머지 3. 관리 4. 인덱스 관리 5. 인덱스 따라 가도록 관리하기 6. 그리고 main, user 어떻게 흘러가는지 파악하기

#include <iostream> #include <stdio.h> using namespace std; const int MAXN = 200000; int CalcFinalSpeed(int N, int *a, int *b, int *p) { int v = 1; for (int i = 0; i < N; i++) { int CurRail = p[i]; v = (int)(((long long)(a[CurRail])*v + b[CurRail]) % 1000000007); } return v; } extern int MinRailSpeed(int N, int *a, int *b); int a[MAXN], b[MAXN]; int main(void) { setbuf(stdout, NULL); freopen("input.txt", "r", stdin); int TestCase; for (scanf("%d", &TestCase); TestCase--;) { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d%d", &a[i], &b[i]); } int answer = MinRailSpeed(N, a, b); static int tc = 0; printf("#%d %d\n", ++tc, answer); } return 0; }

extern int CalcFinalSpeed(int N, int *a, int *b, int *p); #define MAXN 200000 double arr[MAXN]; double sorted[MAXN]; int idx[MAXN]; int sortedIdx[MAXN]; void merge(int left, int mid, int right) { int i, j, k, l; i = left; j = mid + 1; k = left; while (i<=mid && j<=right) { if (arr[i] >= arr[j]) { sortedIdx[k] = idx[i]; sorted[k++] = arr[i++]; } else { sortedIdx[k] = idx[j]; sorted[k++] = arr[j++]; } } if (i > mid) { while (j <= right) { sortedIdx[k] = idx[j]; sorted[k++] = arr[j++]; } } else { while (i <= mid) { sortedIdx[k] = idx[i]; sorted[k++] = arr[i++]; } } for (l = left; l <= right; l++) { idx[l] = sortedIdx[l]; arr[l] = sorted[l]; } } void merge_sort(int left, int right) { int mid; if (left < right) { mid = (left + right) / 2; merge_sort(left, mid); merge_sort(mid + 1, right); merge(left, mid, right); } return; } int MinRailSpeed(int N, int *a, int *b) { int answer = 1; //(ai-1)/bi 로 정렬을 하고, // for (int i = 0; i < N; i++) { arr[i] = (double)(a[i] - 1) / b[i]; idx[i] = i; } merge_sort(0, N - 1); answer = CalcFinalSpeed(N, a, b, idx); return answer; }