信奥赛-刷题笔记-二分篇-T3-P2920Time Management S时间管理者0601

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

二分篇题单

P2920 USACO08NOV Time Management S

https://www.luogu.com.cn/problem/P2920

题目描述

Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on).

To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished.

Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.

作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 N(1\le N\le 1000) 个工作要做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的。

为了高效，约翰列出了所有工作的清单。第 i(1\le i\le N) 个工作需要 T_i(1\le T_i\le 1000) 单位的时间来完成，而且必须在 1\le S_i\le 10^6 或之前完成。现在是 0 时刻。约翰做一份工作必须直到做完才能停止。

所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成。（如果始终无法完成全部任务，输出 -1 ）

输入格式

* Line 1: A single integer: N

第1行：一个整数 N，表示任务的总数。

* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i

第2到第N+1行：每行包含两个用空格分隔的整数：T_i 和 S_i，其中 T_i 表示第i个任务需要的时间，S_i 表示第i个任务必须开始完成的截止时间。

输出格式

* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.

一行：一个整数，表示农夫约翰最晚可以开始工作的时间。如果无法按时完成所有任务，则输出 -1。

输入输出样例 #1

输入 #1

4 
3 5 
8 14 
5 20 
1 16

输出 #1

2

说明/提示

Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of time, respectively, and must be completed by time 5, 14, 20, and 16, respectively.

农夫约翰有4个任务要做，分别需要3、8、5和1个单位的时间来完成，并且这些任务必须分别在时间点5、14、20和16之前完成。

Farmer John must start the first job at time 2. Then he can do the second, fourth, and third jobs in that order to finish on time.

农夫约翰必须在时间点2开始做第一个任务。之后他可以按照第二个、第四个、第三个的顺序完成任务，以确保按时完成所有任务。

代码1

这段代码实现的是一个二分答案 + 贪心模拟的方法来解决 P2920 USACO08NOV Time Management S 这道题。

🧠 题目回顾：

题目大意是说：你有 N 个任务，每个任务需要一定的时间完成，并且必须在某个时间点之前完成。农夫约翰只能一个一个地做任务，不能中断。你要找出他最晚可以从什么时候开始工作，使得所有任务都能按时完成。如果无法完成所有任务，输出 -1。

📌 思路解析：

这个程序使用了以下策略：

✅ 1. 二分答案法（Binary Search on Answer）

• 我们不知道最晚的起始时间是多少，但可以确定范围：
  • 最早是 0
  • 最晚是 1e9（足够大的数）

我们尝试猜测一个起始时间 mid，然后判断是否能在这个时间开始并完成所有任务。

✅ 2. 贪心排序：按截止时间从小到大排序

• 每个任务都有一个截止时间（comes），也就是必须在这之前完成。
• 所以我们应该优先处理截止时间更早的任务（即“越早完不成的越先处理”）。

✅ 3. check 函数验证合法性

• 输入一个假设的起始时间 cnt（也就是可能的答案）
• 然后模拟执行所有任务：
  • 当前时间 tnt = cnt 开始
  • 对于每个任务，如果 当前时间 + 所需时间 <= 截止时间，就继续；
  • 否则说明这个起始时间不合法。

🔍 代码逐行解释

#include <iostream>
#include <cstdio>
using namespace std;

导入头文件，使用标准命名空间。

struct node {
    int start;   // 所需时间 T_i
    int comes;   // 截止时间 S_i
};

定义结构体表示每个任务：start 是所需时间，comes 是截止时间。

struct node que[1000001];
int n;

定义任务数组和任务总数 n。

bool check(int cnt)
{
    int x,y,tnt=cnt;
    for(x=1;x<=n;x++)
    {
        if(que[x].start+tnt <= que[x].comes)
            tnt = que[x].start + tnt;
        else
            return false;
    }
    return true;
}

check(cnt) 判断从时间 cnt 开始是否能完成所有任务。tnt 是当前时间 如果当前时间加上该任务所需时间不超过截止时间，则继续执行下一个任务 否则返回 false，说明这个起始时间不可行

int main()
{
    int right=1000000000,left=1,mid=(left+right)/2;
    int i,j,k,ans=0;
    scanf("%d",&n);

初始化二分查找的左右边界，读取任务数量 n

    for(i=1;i<=n;i++)
        scanf("%d %d",&que[i].start,&que[i].comes);

读取每个任务的 start 和 comes

    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(que[i].comes > que[j].comes)
                swap(que[i],que[j]);

将任务按照 comes（截止时间）升序排序，保证优先处理截止时间更早的任务

    while(left <= right)
    {
        mid = (left + right + 1) / 2;
        if(check(mid))
        {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }

标准的二分查找模板：如果 mid 合法，就尝试找更大的值（因为我们要找最晚的起始时间） 否则缩小右边界

    if(ans != 0)
        cout << ans;
    else
        cout << -1;

输出结果，如果没有找到合法的起始时间，输出 -1

✅ 示例运行

输入：

4
3 5
8 14
5 20
1 16

排序后顺序是：

(3,5), (8,14), (1,16), (5,20)

模拟起始时间为 2：

当前时间: 2 → 加上3 → 5 <= 5 ✔️
当前时间: 5 → 加上8 → 13 <= 14 ✔️
当前时间: 13 → 加上1 → 14 <= 16 ✔️
当前时间: 14 → 加上5 → 19 <= 20 ✔️

✅ 所以 2 是一个合法解，也是最大值，所以输出 2

⚠️ 可能的问题

❗错误点 1：结构体字段名容易混淆

int start;   // 其实是 time_needed（所需时间）
int comes;   // 其实是 deadline（截止时间）

建议改名为 time_needed 和 deadline，避免理解错误。

❗错误点 2：排序逻辑正确，但写法效率低

for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++)
        if(que[i].comes > que[j].comes)
            swap(que[i],que[j]);

这是一个冒泡排序，复杂度是 O(n²)，对于 n=1000 来说没问题，但不如用 sort() 更清晰高效。

✅ 改进建议（更简洁、易懂）

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1005;

struct Job {
    int time_needed;
    int deadline;
};

Job jobs[MAXN];

bool cmp(Job a, Job b) {
    return a.deadline < b.deadline;
}

bool check(int start_time, int n) {
    int current_time = start_time;
    for (int i = 0; i < n; ++i) {
        if (current_time + jobs[i].time_needed > jobs[i].deadline)
            return false;
        current_time += jobs[i].time_needed;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> jobs[i].time_needed >> jobs[i].deadline;

    sort(jobs, jobs + n, cmp);

    int left = 0, right = 1e6, ans = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid, n)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << ans << endl;
    return 0;
}

✅ 总结

如果你还想了解这道题的其他解法（如贪心直接求解、动态规划等），也可以告诉我 😊

🚀 小技巧优化建议

如果你希望进一步提高性能（特别是在大数据量的情况下），可以加上以下两行代码来加速 IO 操作：

ios::sync_with_stdio(false);
cin.tie(nullptr);

这两个语句会关闭 cin 和 cout 与 scanf/printf 的同步，加快输入输出速度。

如果你还有其他问题，比如想了解底层原理、调试方法、或想把这个程序改成支持多组数据等，也可以继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}