自动搬运

查看原文

来自洛谷，原作者为

	CD_Sun_doer jiayou

搬运于2025-08-24 22:54:55，当前版本为作者最后更新于2024-03-18 18:52:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目： P10123 [USACO18OPEN] Milking Order B

主要思路：

本题主要思想是贪心，模拟起来分类讨论情况容易掉点，需要细心与耐心，贪心策略倒是不难想：

1. 最一般的情况，奶牛 1 号不在 $m$ 或 $k$ 中，此时将奶牛 1 越靠前排越好 （还要把整个社会阶层的尽可能往 后 排）。
2. 特殊情况奶牛 1 在 $k$ 中，则直接输出即可。
3. 奶牛 1 如果在 $m$ 社会阶层中，则将 1 号及 1 号之前成员全部尽可能往前排。

如果还不懂可以看着代码自己推演一下，代码注释详细：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int cow_pos[111];//奶牛所在位置 
bool pos_cow[111];//第i个位置是否有奶牛 
int a[111];//m头有社会阶层的奶牛，挤奶先后顺序已定 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		int cow,pos;
		cin>>cow>>pos;
		pos_cow[pos]=true;
		cow_pos[cow]=pos;
		if(cow==1){
			//特殊情况,一号奶牛位置已定直接输出 
			cout<<pos;
			return 0;
		}
	}
	int now_pos=n;//当前所在位置
	//倒叙遍历 
	for(int i=m;i>=1;i--){
		if(cow_pos[a[i]]){
			now_pos=cow_pos[a[i]]-1;
			//如果奶牛a[i]位置已定则当前位置为a[i]位置前一位
			continue;
		}
		if(a[i]==1){//__如果社会阶层中有1则尽可能往前排 
			int cnt=1,begi=1;
			for(int j=1;j<i;j++){//1号及社会阶层中1号之前的成员都尽可能往前排 
				if(cow_pos[a[j]]){
					begi=cow_pos[a[j]]+1;
					cnt=1;//社会阶层中1号前的成员如果有确定位置的要重置cnt 
					continue;
				}++cnt;
			}
			for(int j=begi;j<=n;j++){
				if(!pos_cow[j]){
					pos_cow[j]=true;
					cnt--;
				}
				if(!cnt){//社会阶层中1号之前奶牛位置已定，则直接输出 
					cout<<j;
					return 0;
				}
			}
		}else{//__否则尽可能排的靠后 
			while(pos_cow[now_pos]){
				now_pos--;
			}
			pos_cow[now_pos--]=true;
		}
	}
	//按照策略排好后，从前往后找空位，越靠前越好 
	for(int i=1;i<=n;i++){
		if(!pos_cow[i]){//找到直接输出 
			cout<<i;
			return 0;
		}
	}
	return 0;
} 

也是侥幸拿下总运行时间的最优解之一。