[SwExpertAcademy] 롤러코스터

문제 출처 :

https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxxej6Ae4DFAW4#

알고리즘 분석 :

문제 해결에 필요한 사항

1. 정렬 

이 문제는 av + b가 가장 크게 나타나도록 해야한다.

따라서 정렬할 때 a1,b1이 있고 a2,b2가 있다면

a1(a2*v + b2) + b1 과 a2(a1*v + b1) + b2중 무엇이 큰지 비교해야한다.

따라서 내림차순 정렬조건은 a1(a2*v + b2) + b1 > a2(a1*v + b1) + b2가 되고

a1*a2*v +a1*b2 + b1 > a1*a2*v + a2*b1 + b2

a1*b2 - b2 > a2*b1 -b1

b2*(a1 - 1) > b1*(a2 - 1)이 된다.

소스 코드 : 

#include <iostream>
#include <algorithm>
 
#define MOD 1000000007
 
using namespace std;
 
typedef long long ll;
 
struct PAIR {
    ll first, second;
};
 
PAIR arr[200002];
 
bool comp(const PAIR &a, const PAIR &b) {
    return b.second * (a.first - 1) > a.second * (b.first - 1);
}
int main() {
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            scanf("%lld %lld", &arr[i].first, &arr[i].second);
 
        sort(arr, arr + n, comp);
 
        ll v = 1;
 
        for (int i = 0; i < n; i++)
            v = ((arr[i].first*v) % MOD + arr[i].second) % MOD;
 
        printf("#%d %lld\n", tc, v);
    }
    return 0;
}