NC24284. [USACO 2018 Ope B]Milking Order
描述
首先，由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。比方说，如果奶牛3有最高的地位，奶牛2位于中等地位，奶牛5是低地位，那么奶牛3会最早挤奶，然后是奶牛2，最后是奶牛5。
然后，有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。比方说，奶牛4可能坚持要在所有奶牛中的第二位挤奶。
幸运的是，Farmer John总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。
不幸的是，奶牛1最近生病了，所以Farmer John想要尽早给这头奶牛挤奶，使得她可以回到牛棚获得急需的休息。请帮助Farmer John求出奶牛1可以在挤奶顺序中出现的最早位置。
输入描述
第一行包含N，M（1≤M<N），和K（1≤K<N），表示Farmer John有N头奶牛，其中M头形成了社会阶层，K头需要在挤奶顺序中处于一个特定的位置。下一行包含M个不同的整数mi（1≤mi≤N）。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。下面K行，每行包含两个整数ci（1≤ci≤N）和pi（1≤pi≤N），表示奶牛ci一定要在第pi位进行挤奶。
输入数据保证在这些限制之下，Farmer John能够建立一个符合要求的挤奶顺序。
输出描述
输出奶牛1可以在挤奶顺序中出现的最早位置。
示例1
输入:
6 3 2 4 5 6 5 3 3 1
输出:
4
说明:
在这个例子中，Farmer John有六头奶牛，其中奶牛1生病了。他的挤奶顺序应该为奶牛4在奶牛5之前，奶牛5在奶牛6之前。此外，Farmer John必须要第一个给奶牛3挤奶，第三个给奶牛5挤奶。C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 492K, 提交时间: 2019-06-29 22:13:07
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,K,a[N],b[N],pos[N];
int main()
{
scanf("%d%d%d",&n,&m,&K);
int fl=0;
for(int i=1;i<=m;i++){
scanf("%d",&b[i]);
if(b[i]==1) fl=i;
}
for(int i=1;i<=K;i++){
int x,y;scanf("%d%d",&x,&y);
a[y]=x;pos[x]=y;
if(x==1){printf("%d",y);return 0;}
}
for(int j=n,i=m;i&&i!=fl;i--){
if(pos[b[i]]) j=pos[b[i]];
else while(a[j]) j--;
a[j--]=b[i];
}
if(!fl)
for(int i=1;i<=n;i++)
if(!a[i]){printf("%d",i);return 0;}
for(int i=1,j=1;i<=fl;i++){
if(pos[b[i]]) j=pos[b[i]];
else while(a[j]) j++;
a[j++]=b[i];
if(i==fl) printf("%d",j-1);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2019-06-29 11:27:43
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,m,k,c[1100],xx,p[1100],b[1100],now,inq;
int main(){
scanf("%d%d%d",&n,&m,&k);
fo(i,1,m){
scanf("%d",&p[i]);
if (p[i]==1) inq=i;
}
fo(i,1,k){
scanf("%d",&xx);
scanf("%d",&c[xx]);
b[c[xx]]=xx;
}
if (c[1]){
printf("%d\n",c[1]);
return 0;
}
if (inq){
fo(i,1,inq){
if (c[p[i]]){
now=c[p[i]];
continue;
}
while (b[now+1]) now++;
now++;
}
printf("%d\n",now);
}else{
now=n+1;
fd(i,m,1){
if (c[p[i]]){
now=c[p[i]];
continue;
}
while (b[now-1]) now--;
b[--now]=p[i];
}
fo(i,1,n) if (!b[i]){
printf("%d\n",i);
break;
}
}
return 0;
}