题解 | 挤奶顺序-牛客假日团队赛4B题

B-挤奶顺序_牛客假日团队赛4

https://ac.nowcoder.com/acm/contest/947/B

题目描述

Farmer John的 $N$ 头奶牛 $（2≤N≤100）$ ，方便起见仍然编号为 $1…N$ ，正好闲得发慌。因此，她们发展了一个与Farmer John每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究，Farmer John发现这个结构基于两个关键特性。

首先，由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。比方说，如果奶牛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$ 个不同的整数 $m_i（1≤m_i≤N）$ 。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。下面 $K$ 行，每行包含两个整数 $c_i（1≤c_i≤N）$ 和 $p_i（1≤p_i≤N）$ ，表示奶牛 $c_i$ 一定要在第 $p_i$ 位进行挤奶。

输入数据保证在这些限制之下，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挤奶。

FJ必须第一个给奶牛3挤奶，由于奶牛4必须要在奶牛5之前，奶牛4一定是第二个挤奶的，然后奶牛5第三个。于是，奶牛1最早在挤奶顺序中出现的位置是第四个。

解答

确定的奶牛的挤奶位置就直接填上，然后我把一系列顺序以1为分界线分成两边，1右边的点尽可能往右边放，1左边的点尽可能的往左边放，如果1没出现，那么默认1是第一顺序挤奶，放完之后根据1左边一位和右边一位的限制区间，找一个最早挤奶的位置，还有就是搜之前要先确定第一个和最后一个的最左或最右顺序，不然其他的都没办法确定。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int ding=105;
struct node{
    int val,posi;
//  node(){
//      val=posi=0;
//  }
}a[ding];
int cow[ding],posi[ding];
int main()
{
    std::ios::sync_with_stdio(false);
    int n,m,k,aa,b,i,flag1=0,j;
    scanf("%d %d %d",&n,&m,&k);
//  a[1].val=1;
    for(i=1;i<=m;i++){
        scanf("%d",&a[i].val);
    }
    for(i=0;i<k;i++){
        scanf("%d %d",&aa,&b);
        if(aa==1){
            flag1=1;
        }
        cow[aa]=b;
        posi[b]=aa;
    }
    if(flag1){
        printf("%d\n",cow[1]);
        return 0;
    }
//  if(flag){
//     
//  }
    if(a[m].val!=1){
        if(cow[a[m].val]>0)
            a[m].posi=cow[a[m].val];
        else {
            int k=n;
            while(posi[k]){
                k--;
            }
            a[m].posi=k;
            posi[k]=a[m].val;
            cow[a[m].val]=k;
        }
    }
     
    for(i=m;i>=1;i--){
        if(a[i].val==1)break;
        if(cow[a[i].val]>0){
            a[i].posi=cow[a[i].val];
        }
        else{
            if(a[i+1].posi>0){
                 
                int j=a[i+1].posi-1;
//              printf("j  %d %d\n",a[i].val,j);
                while(j>0&&posi[j]){
                    j--;
                }
                a[i].posi=j;
                posi[j]=a[i].val;
                cow[a[i].val]=j;
            }
             
        }
    }
//  printf("iii %d\n",i);
    if(1<i){
        if(cow[a[1].val])
            a[1].posi=cow[a[1].val];
        else {
            int k=1;
            while(posi[k]){
                k++;
            }
            a[1].posi=k;
            posi[k]=a[1].val;
            cow[a[1].val]=k;
        }
    }
    for(j=1;j<i;j++){
        if(cow[a[j].val]>0){
            a[j].posi=cow[a[j].val];
        }
        else{
            if(a[j-1].posi>0){
                int k=a[j-1].posi+1;
//              printf("j  %d %d\n",a[i].val,j);
                while(k<=n&&posi[k]){
                    k++;
                }
                a[j].posi=k;
                posi[k]=a[j].val;
                cow[a[j].val]=k;
            }
             
        }
    }
//  for(i=1;i<=n;i++){
//      printf("posi  %d\n",posi[i]);
//  }
    int L=1,R=n;
    for(i=1;i<=m;i++){
        if(a[i].val==1){
            if(i<m)R=a[i+1].posi-1;
            if(i>1)L=a[i-1].posi+1;
            break;
        }
    }
    for(i=L;i<=R;i++){
        if(posi[i]==0){
            printf("%d\n",i);
            break;
        }
    }
 
 return 0;
}

来源：甦萌