admin LV 10 SU @ 2026-9-3 19:35:42

P5894 [IOI 2013] robots 机器人

二分答案。

题目大意

有 $a$ 个弱机器人，第 $i$ 个只能运重量不大于 $x_i$ 的物品；有 $b$ 个小机器人，第 $i$ 个只能运体积不大于 $y_i$ 的物品。有 $t$ 个物品，第 $i$ 个物品重 $w_i$ ，体积为 $s_i$ 。

需要运送所有 $t$ 个物品，最小化使用次数最多的机器人的次数。

题意分析

由题目分析出关键词“最小化最大值”，可以使用二分答案二分最小值。可以先从弱机器人入手，容易分析得到两个物品都能被同一个弱机器人运走，二选一选体积大的物品一定不劣。因为选体积小的物品留下体积大的可能会在小机器人运送时出现没有小机器人能运体积大的那个物品并不是最优。

同时，为保证限制大的弱机器人不会被重量小的物品占用次数，应该将弱机器人限制从小到大排序，并且将物品按重量从小到大排序，小的配小的，大的配大的。

遍历弱机器人，将没有被选择且能被当前机器人选择的物品的体积入大根堆，每个弱机器人一定将次数使用完，取堆顶，即体积大的运走。

剩下的物品用小机器人送，由于堆顶是体积最大的物品，所以小机器人应该按限制从大到小排序，同样地，大的配大的，小的配小的。

时间复杂度 $\mathcal{O}(T \log^2 T)$ 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef OFFLINE_RUN
struct Timer { 
    chrono::high_resolution_clock::time_point start; 
    Timer() { start = chrono::high_resolution_clock::now(); } 
    ~Timer() { 
        auto end = chrono::high_resolution_clock::now(); 
        auto duration = chrono::duration_cast<chrono::milliseconds>(end - start); 
        fprintf(stderr, "\033[32m%lldms\033[0m\n", 1ll * duration.count()); 
} } timer;
#endif

const int T = 1e6 + 10, R = 5e4 + 10;
struct toy {
    int w, s;
    toy() {}
    toy(int w, int s) : w(w), s(s) {}
} p[T];
int x[R], y[R];
int a, b, t;
priority_queue<int> q;

bool chk(int limit) {
    while (!q.empty()) {
        q.pop();
    }
    int cur = 1;
    for (int i = 1; i <= a; i++) { // weak(weight) robot
        while (cur <= t && p[cur].w < x[i]) {
            q.push(p[cur++].s);
        }
        int cnt = 0;
        while (!q.empty() && cnt++ < limit) {
            q.pop();
        } 
    }
    while (cur <= t) {
        q.push(p[cur++].s);
    }
    for (int i = 1; !q.empty() && i <= b; i++) { // small(size) robot
        int cnt = 0;
        while (!q.empty() && q.top() < y[i] && cnt++ < limit) {
            q.pop();
        }
    }
    return q.empty();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b >> t;
    for (int i = 1; i <= a; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= b; i++) {
        cin >> y[i];
    }
    for (int i = 1, w, s; i <= t; i++) {
        cin >> w >> s;
        p[i] = toy(w, s);
    }
    sort(x + 1, x + a + 1); // weak(weight) low->high
    sort(y + 1, y + b + 1, greater<int>()); // small(size) high->low
    sort(p + 1, p + t + 1, [](toy x, toy y) {
        return x.w < y.w;
    }); // toy.weight low->high
    int l = 1, r = t, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (chk(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

AC Record

admin LV 10 SU @ 2026-9-3 19:34:19

P5894 [IOI 2013] robots 机器人题解

::::warning[题外话]

某模拟赛赛时乱写的 $51$ pts STL 代码放送

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define nbsp cerr<<'\n'
#define debugx(x) cerr<<#x<<" : "<<x<<'\n'
#define debuga(x,l,r) cerr<<#x<<" : ";for(int i=l;i<=r;i++)cerr<<x[i]<<' ';cerr<<'\n'
#define debugp(x,i) cerr<<#x<<'['<<i<<']'<<" : "<<x[i]<<'\n'
#define flin(s) char ccccc1[100]=#s;freopen(strcat(ccccc1,".in"),"r",stdin)
#define flout(s) char ccccc2[100]=#s;freopen(strcat(ccccc2,".out"),"w",stdout)
#define clr(x,y) memset(x,y,sizeof x)

const int T=1e6+5,N=5e4+5;
int t,n,m,a[N],b[N];
struct bot
{
	int w,s,ix;
}p[T],pw[T],ps[T];
bool visp[T];
map<int,int> visa,visb;
multiset<int> sta,stb;

bool check(int x)
{
	visa.clear();
	sta.clear();
	visb.clear();
	stb.clear();
	memset(visp,0,sizeof visp);
	for(int i=1;i<=n;i++)
		sta.insert(a[i]);
	for(int i=1;i<=m;i++)
		stb.insert(b[i]);
//	debugx(x);
	for(int i=1;i<=t;i++)
	{
		if(sta.empty() && stb.empty())
			return 0;
		auto ixa=sta.upper_bound(ps[i].w);
		auto ixb=stb.upper_bound(pw[i].s);
		if(ixa==sta.end() && ixb==stb.end())
			continue;
//		if(ixa!=sta.end())
//		debugx(*ixa);
//		if(ixb!=stb.end())
//		debugx(*ixb);
		if(ps[i].ix==pw[i].ix)
		{
			if(ixa==sta.end() && !visp[pw[i].ix])
			{
				visb[*ixb]++;
				if(visb[*ixb]>=x)
					stb.erase(ixb);
				visp[pw[i].ix]=1;
//				cout<<"1\n";
				continue;
			}
			if(ixb==stb.end() && !visp[ps[i].ix])
			{
				visa[*ixa]++;
				if(visa[*ixa]>=x)
					sta.erase(ixa);
				visp[ps[i].ix]=1;
//				cout<<"2\n";
				continue;
			}
			if(*ixa>*ixb && !visp[pw[i].ix])
			{
				visb[*ixb]++;
				if(visb[*ixb]>=x)
					stb.erase(ixb);
				visp[pw[i].ix]=1;
//				cout<<"3\n";
			}
			else if(!visp[ps[i].ix])
			{
				visa[*ixa]++;
				if(visa[*ixa]>=x)
					sta.erase(ixa);
				visp[ps[i].ix]=1;
//				cout<<"4\n";
			}
		}
		else
		{
			if(ixa!=sta.end() && !visp[ps[i].ix])
			{
				visa[*ixa]++;
				if(visa[*ixa]>=x)
					sta.erase(ixa);
				visp[ps[i].ix]=1;
			}
			if(ixb!=stb.end() && !visp[pw[i].ix])
			{
				visb[*ixb]++;
				if(visb[*ixb]>=x)
					stb.erase(ixb);
				visp[pw[i].ix]=1;
			}
//			cout<<"5\n";
		}
	}
	for(int i=1;i<=t;i++)
		if(!visp[i])
			return 0;
	return 1;
}

signed main()
{
	fastio;
	flin(robots);
	flout(robots);
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=m;i++)
		cin>>b[i];
	sort(b+1,b+m+1);
	for(int i=1;i<=t;i++)
		cin>>p[i].w>>p[i].s,ps[i]=pw[i]=p[i],p[i].ix=pw[i].ix=ps[i].ix=i;
	sort(pw+1,pw+t+1,[](bot x,bot y){return x.w>y.w;});
	sort(ps+1,ps+t+1,[](bot x,bot y){return x.s>y.s;});
	int l=1,r=t,ans=-1,mid;
	while(l<=r)
	{
		mid=l+(r-l)/2;
		if(check(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	cout<<ans<<'\n';
	return (0.0);
}

::::

题意

一共有 $t$ 个玩具 $p_{1 \sim t}$ ，分别给出每个的重量和体积。现有 $n$ 个弱 bot 和 $m$ 个小 bot，弱 bot 有重量上限 $w_{1 \sim n}$ ，小 bot 有体积上限 $s_{1 \sim m}$ ，这些上限都是小于。要求找到所有 bot 使用次数最大值最小的方案，求出这个最小值。

思路

整理题意后一眼二分答案。设当前要判断的值为 $x$ ，说明每个 bot 最多使用 $x$ 次。

首先，先让弱 bot 处理。肯定让重量小的玩具先被处理啦，所以让 $p$ 按重量小到大排序，当然， $w$ 也得从小到大排序。

仔细思考（研究样例！一定要养成习惯！）容易得出，每个弱 bot 处理它能处理的重量时，处理体积最大的玩具是最优的，可以让之后小 bot 处理的更多，所以考虑优先队列整大根堆。
每次处理时，遍历当前未处理的玩具（已按重量排序）直到不能处理，往堆里塞这个玩具的体积，遍历结束后再取堆顶的几个能处理且体积最大的弹出，也就是处理。
这个步骤需要较强 ~~（其实是我不会）~~ 的代码实现能力，所以待会代码详细解释。

弱 bot 处理完，我们发现获得了一个弱 bot 没有处理，剩下的所有玩具的重量。哇！这对我们处理小 bot 非常友好，每次处理直接用上限最高的小 bot 配堆顶就行了！前提是要把小 bot 上限 $s$ 从大到小排序。这个模拟就好。

~~看代码吧，表达能力极差。~~

Code

:::success[by elainya_stars]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define nbsp cerr<<'\n'
#define debugx(x) cerr<<#x<<" : "<<x<<'\n'
#define debuga(x,l,r) cerr<<#x<<" : ";for(int i=l;i<=r;i++)cerr<<x[i]<<' ';cerr<<'\n'
#define debugp(x,i) cerr<<#x<<'['<<i<<']'<<" : "<<x[i]<<'\n'
#define flin(s) char ccccc1[100]=#s;freopen(strcat(ccccc1,".in"),"r",stdin)
#define flout(s) char ccccc2[100]=#s;freopen(strcat(ccccc2,".out"),"w",stdout)
#define clr(x,y) memset(x,y,sizeof x)

const int T=1e6+5,N=5e4+5;
int t,n,m,w[N],s[N];
struct bot
{
	int w,s;
	bool friend operator<(bot x,bot y) {return x.w<y.w;}
}p[T];
priority_queue<int> q; // 存储当前要处理的所有玩具的体积

bool check(int x)
{
	while(!q.empty())
		q.pop(); // 清空
	int now=1; // 下面用来遍历p的
	for(int i=1;i<=n;i++)
	{
		while(now<=t && p[now].w<w[i])
		// 当前的玩具重量可以用这只（第i只）弱bot处理，小于处理上限
			q.push(p[now++].s);
		// 就贪心的去把这个玩具放进处理列表
		// 放的是体积，因为优先处理体积大的最优，上面解释过
		
		for(int j=1;j<=x;j++) // 最多使用x（原来的mid）个弱bot
		{
			if(q.empty()) // 列表没了
				break;
			q.pop();
		}
	}
	while(now<=t)
	// 把剩余没放过的所有体积放进处理列表，为了下一步小bot选玩具
		q.push(p[now++].s);
	for(int i=1;i<=m;i++)
	{
		if(q.empty()) // 列表空了处理干净了
			break;
		for(int j=1;j<=x;j++) // 最多使用x（原来的mid）个小bot
		{
			if(q.empty() || q.top()>=s[i])
			// 空或列表里的体积大于等于能处理范围
			// 说明这个型号的小bot搞不了这个玩具，直接退出遍历
				break;
			q.pop(); // 处理这个玩具
		}
	}
	return q.empty(); // 若列表空了说明处理干净了返回true
}

signed main()
{
	fastio;
//  flin(robots);
//  flout(robots);
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=m;i++)
		cin>>s[i];
	for(int i=1;i<=t;i++)
		cin>>p[i].w>>p[i].s;
	sort(w+1,w+n+1); // 小到大排序
	sort(s+1,s+m+1,[](int x,int y){return x>y;}); // 大到小排序
	sort(p+1,p+t+1); // 按重量小到大排序
	int l=1,r=t,ans=-1,mid; // ans初始-1，无解直接输出
	while(l<=r) // 二分板子
	{
		mid=(l+r)>>1;
		if(check(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	cout<<ans<<'\n';
	return (0.0);
}

:::

给我赞赞 qwq

ID

4913

时间

2000ms

内存

64MiB

难度

标签

递交数

已通过

上传者

Hydro

2 条题解