题解：P12034 [USTCPC 2025] Introduction to ICPC

chenyuan3 · 2025-04-10 19:03:18 · 题解

思路：设 i 为获得当前奖项的最后一名。

• 上界：显然是获得该奖项的最低分；
• 下界：分情况讨论：
  • 观察样例发现当 y_{i+1}>0 时答案为 x_{i+1} 和 y_{i+1}-1；
  • 显然罚时不能是负数，所以当 y_{i+1}=0 时通过数只能变高为 x_{i+1}-1，罚时取最大，考虑所有题都在 299 分钟通过，且交满了 300\times30 发提交，除了最后一发通过以外，其它都计算罚时。故最大的罚时为 299(x_{i+1}+1)+[9000−(x_{i+1}+1)]×20=180000+279(x_{i+1}+1)。

代码：（AC 记录）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;
ll a, b, c, d, p[maxn], t[maxn];
void work(ll n) // 用于输出 n 为这一奖项的最后一名的上界与下界
{
    cout << p[n] << ' ' << t[n] << ' ';
    if (t[n + 1] > 0)
    {
        cout << p[n + 1] << ' ' << t[n + 1] - 1 << endl;
    }
    else
    {
        cout << p[n + 1] + 1 << ' ' << 180000 + (p[n + 1] + 1) * 279 << endl;
    }
}
void solve()
{
    cin >> a >> b >> c >> d;
    for (ll i = 1; i <= a + b + c + d; i++)
    {
        cin >> p[i] >> t[i];
    }
    work(a);
    work(a + b);
    work(a + b + c);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // ll t; cin >> t; while (t--)
    solve();
    return 0;
}