2019 ICPC Malaysia National

翻译 岛田小雅

C. I Don't Want To Pay For The Late Jar!

出题人

IT 支持部门的 Nina 小姐需要你解决一个生活中的小问题。她可以在任何时刻去吃午饭，但只能花 \(S\) 分钟，\(S\) 的大小取决于当天的工作量。如果她迟到了，每迟到 \(1\) 分钟就要被罚款 \(1\) \(RM\)。

她列了个她最爱餐厅的清单，以及在每个餐厅的用餐时间 \(t_i\) \((1\leqslant{t_i}\leqslant{10^9})\)。她也给每个餐厅列了个值 \(f_i\)，代表她在那个餐厅吃饭的罚款预算是 \(f_i\) 。

举个例子。Nina 去餐厅 \(x\) 吃饭，如果 \(t_x\leqslant{S}\)，她就节约了 \(f_x\) \(RM\)。如果 \(t_x>S\)，她就只能节约 \(f_x-(t_x-S)\)。

请帮她找出能节约最多钱的餐厅。

对了，她一天只能去一家餐厅吃午饭。

输入格式

第一行是一个整型 \(D\) \((1\leqslant{D}\leqslant{10})\) 代表天数。

第二行有两个数，\(N\) \((1\leqslant{N}\leqslant{10^4})\) 和 \(S\) \((1\leqslant{S}\leqslant{10^9})\)，它们被用空格分开，代表餐厅的个数和她当天被允许的午饭时间。

接下来的 N 行，每一行有两个数字。\(f_i\) \((1\leqslant{f_i}\leqslant{10^9})\) 和 \(t_i\) \((1\leqslant{t_i}\leqslant{10^9})\)，它们被用空格分开，表示餐厅 \(i\) 的信息。

输出格式

输出 \(N\) 行，一行一个整数，代表 Nina 在第 \(i\) 天最多能节约多少 \(RM\)。你需要用到格式：Case #i:。

样例

输入

2
2 5
3 3
4 5

1 5
1 7

输出

Case #1: 4
Case #2: -1

题解

作者 岛田小雅

直接把所有餐厅节约的钱算出来然后找最大值就行了。

AC 代码

作者 岛田小雅

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+2;
const int INF = 0x7fffffff;
int D, n, S;
int Case;
int ans;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> D;
    while(++Case <= D)
    {
        ans = -INF;
        cin >> n >> S;
        for(int i = 1; i <= n; i++)
        {
            int tmpf, tmpt;
            cin >> tmpf >> tmpt;
            ans = max(ans,tmpf-max(0,tmpt-S));
        }
        cout << "Case #" << Case << ": " << ans << '\n';
    }
    return 0;
}