自动搬运

查看原文

来自洛谷，原作者为

	2024sdhkdj **

搬运于2025-08-24 21:27:46，当前版本为作者最后更新于2023-07-11 22:41:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[USACO05FEB] Feed Accounting S题解

1、题意描述

依照题面：已知今日日期 $D$ 和最近一次饲料运到至今所消耗的饲料 $F2\sim F1$。有 $C$ 头牛，每头牛每天都吃掉恰好 $1$ 千克饲料，对于每头牛，有一个开始日期 $ate$ 和一个结束日期 $Left$，求上一船饲料运到的时间。

2、思路

此题正解是差分，但我却阴差阳错想到了二分答案。此题的二分答案的思路是：初始化左端点 $l=0$，右端点 $r=d$ （今天日期），然后开始二分答案 $mid$。对于每次二分到的 $mid$，记录以它为上一船饲料运到的时间所消耗的饲料，然后判断其是否与 $F1-F2$ 相等，最后记录答案并输出即可。此算法复杂度为 $O(n \log n)$。

如有解释不当之处，请辅以代码理解！

3、贴代码：

#include<bits/stdc++.h>
using namespace std;
int c,f1,f2,d,ate[110],Left[110],ans;
bool check(int x){//检查此答案是否合法
	int jl=0;
	for(int i=1;i<=c;i++){
		if(ate[i]<=x){
			if(Left[i]>=x&&Left[i]<=d)
				jl+=Left[i]-x+1;
			else if(Left[i]>d)
				jl+=d-x+1;	
		}
		else{
			if(ate[i]<=d){
				if(Left[i]>=d)
					jl+=d-ate[i]+1;
				else
					jl+=Left[i]-ate[i]+1;	
			}
		}			
	}
	return jl>=f1-f2;
}
int main()
{
    ios::sync_with_stdio(NULL);//快读
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>c>>f1>>f2>>d;
    for(int i=1;i<=c;i++)
    	cin>>ate[i]>>Left[i];//ate表示此牛来的日期，Left表示离开日期
    int l=1,r=d,mid;
    while(l<=r){//二分答案
    	mid=(l+r)/2;
    	if(check(mid)){//如果此答案满足，则记录下来
    		ans=mid;
    		l=mid+1;
	}
	else
		r=mid-1;
	} 
	cout<<ans;
	return 0;
}

AC记录