Living-Dream 系列笔记 第6期

模拟赛。 寄。

T1

对于每次询问，二分查找数组中对应值的原下标即可，因此需要用结构体存储原始数据和原始下标。这当然是比较麻烦的做法。

另一种做法则是开一个 map 替代桶来存储数组中每个元素的下标，对于每个询问输出即可。

另外值得注意的是，本题默认询问之间相互独立。

时间复杂度均为 \(O(q \log n)\)。

方法一代码、方法二代码。

T2

\(Link\)。

T3

很多人第一直觉想到对所有任务排序后第一项任务的截止时间 \(-\) 完成时长即为答案。其实不然：

如图，若从第一项任务的截止时间 \(-\) 完成时长的这一时刻开始干，则结束后就不够完成第二项任务了，因此我们需要将时间继续提早。

于是我们就想到了二分答案，原因：

• 本题是要在能够完成所有任务的情况下找到最迟的开始时间，即在限制条件下找最大值。

• 同时，本题也具有十分明显的单调性：若从 \(x\) 时刻开始做能做完，则从 \(< x\) 的时刻开始做仍然能做完；若从 \(x\) 时刻开始做不完，则从 \(>x\) 的时刻开始仍然做不完。

证明了可以使用二分答案后，我们考虑如何设计 check 函数：

• 首先需要对数组按照截止时间排序；

• 接着模拟一遍完成任务的过程，若超过了当前任务的截止时间则返回 \(0\)，否则返回 \(1\)。

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

int n;
pair<int,int> p[1031];
bool cmp(pair<int,int> &a,pair<int,int> &b){
	return a.second<b.second;
}

bool check(int x){
	int tme=x;
	for(int i=1;i<=n;i++){
		tme+=p[i].first;
		if(tme>p[i].second) return 0;
	}
	return 1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second;
	sort(p+1,p+n+1,cmp);
	
	int l=-1,r=1e6+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

习题

考虑二分 \(R\) 的值。

在 check 函数中仅需记录一个即将被炸的位置 \(p\) 以及已经投放的奶牛数 \(s\)，循环 \(1 \sim n\)，若 \(p+mid < a_i\)（即无法炸掉 \(a_i\)），则令 \(s \gets s+1\) 且 \(p=a_i\)。在循环过程中若 \(s>k\)，则返回 \(0\)，若循环结束后 \(s \le k\)，则返回 \(1\)。

注意排序。

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

int n,k;
int a[50031];

bool check(int x){
    int s=0,p=-1e9;
    for(int i=1;i<=n;i++){
        if(p+x<a[i]){ 
            s++,p=a[i]+x;
            if(s>k) return 0;
        }
    }
    return 1;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    
    int l=-1,r=1e9+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r;
    return 0;
}