题解：P10123 [USACO18OPEN] Milking Order B

· · 题解

题目： 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;
}

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