POJ 3863 - Business Center

http://poj.org/problem?id=3863

概要

m 個のエレベータがあり，i 番目のエレベータには u[i] 階分上るボタンと d[i] 階分下るボタンがついている． 最初は 0 階にいて，n 回押した後にいる階を最小化してその値を答える．

この建物は非常に高いのでどれだけ上っても構わないが，0階より下には行けない． 一度あるエレベータに乗ったら，それ以降そのエレベータから降りてはならない． 最終的な階は 0 階より上でなければならない．

制約

• 1 <= n <= 1000000
• 1 <= m <= 2000

解法

立式して解いてみると，i 番目のエレベータに関して最小化するには，下のボタンを (n*u[i] - 1) / (u[i] + d[i]) 回押せばいいことがわかる． あとはこれの最小値を答えればいい．

 1 #include <cstdio>
 2 #include <limits>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 long long solve(int u, int d, int N)
 7 {
 8   const long long m = (static_cast<long long>(N)*u-1LL)/(u+d);
 9   const long long n = N - m;
10   return u*n - m*d;
11 }
12 
13 int main()
14 {
15   int N, M;
16   scanf("%d %d", &N, &M);
17   long long ans = numeric_limits<long long>::max();
18   for (int i = 0; i < M; i++) {
19     int u, d;
20     scanf("%d %d", &u, &d);
21     ans = min(ans, solve(u, d, N));
22   }
23   printf("%lld\n", ans);
24   return 0;
25 }