C++ / ACM 自学笔记 · v5.0

P1085 不高兴的津津

原题入口

对应章节:三、解题方法论:从题意到代码 → (八) 用不变量和反例检查推导。

(一) 任务与输出目标

找出超过八小时且上课总时长最大的那一天,同样长时选最早一天。

(二) 建模与推导

按星期顺序扫描,把目前最长时间初始化为 8、答案初始化为 0。新一天的时间严格大于目前最长时间时才替换;同样长时保留之前的答案,自然选择更早一天。

(三) 手算与过程

第一天与第二天都是 9 小时,第一天保留下来;所有天都不超过 8 时答案仍为 0。

(四) 带注释实现

完整源文件

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve() {
    int best = 8, day = 0;
    for (int i = 1; i <= 7; ++i) {
        int school, extra;
        cin >> school >> extra;
        if (school + extra > best) { // 只在更长时替换,保留最早的同分日。
            best = school + extra;
            day = i;
        }
    }
    cout << day << '\n';
}

signed main() {
    ios::sync_with_stdio(false); // 关闭同步,使用 cin 与 cout 完成输入输出。
    cin.tie(0), cout.tie(0);

    int T = 1; // 本题读入一组数据。
    // cin >> T; // 题目给出测试组数时开启,并在 solve 中处理一组。
    while (T--)
        solve();
}

(五) 复杂度

固定扫描七天,时间 \(O(1)\),额外空间 \(O(1)\)。

返回本章题解索引 · 返回全部题号索引

查阅笔记正文与全部题解 · Ctrl / ⌘ K