P3034 [USACO11DEC] Cow Photography G/S 题解

2023/10/02 Blog

模拟赛考到的题,来发题解。

解法

因为题中说如果一头奶牛在拍其中一张照片时移动了,它在拍其他四张照片的时候都不会移动,所以设有两头奶牛 $A$ 和 $B$,其中 $A$ 应该在 $B$ 的前面,那只有当奶牛 $A$ 跑到 $B$ 后面或者 奶牛 $B$ 跑到 $A$ 前面这两种情况能让两头奶牛的相对位置互换,所以对于这 $5$ 张照片,如果一头奶牛在另一头奶牛之前的位置超过 $5-2=3$ 次,则表明这头奶牛应该在那头奶牛的前面,他们的相对位置就确定下来了。我们只需要确定所有奶牛的相对位置即可。知道了所有奶牛的相对位置即可知道所有奶牛的绝对位置。这个可以在排序的过程中实现。

时间复杂度 $\mathcal{O}(n \log n)$,瓶颈在于排序。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
    /*
    fast Input/
    */
};
using namespace fast_IO;
int n;
struct cow
{
    int x,pos[6];
    inline bool operator<(const cow &rhs) const
    {
        int cnt=0;
        for(int i=1;i<=5;i++) if(pos[i]<rhs.pos[i]) cnt++;
        return cnt>=3;
    }
};
cow a[20010];
unordered_map<int,int> mp;
int main()
{
    read(n);
    for(int i=1,x;i<=n;i++) read(x),a[i].x=x,a[i].pos[1]=i,mp[x]=i;
    for(int i=2,x;i<=5;i++) for(int j=1;j<=n;j++) read(x),a[mp[x]].pos[i]=j;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) write(a[i].x),write('\n');
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}
对我博客最大的鼓励来自于你的评论(什么玩梗),欢迎选择 来回复, 也可以在 GitHub discussion 留言。

Search

    公告

    博主这下真摆烂了。我下辈子也不碰 Jekyll 和 MathJax 了!
    留言板,现在博主的精神状态非常好,有事烧纸。

    联系方式

    QQ: 33299235
    email: 33299235@qq.com
    Gmail: scp020.cn@gmail.com

    本人的其它个人主页

    洛谷
    CSDN

    友链

    拜谢stevehim(已退役,祝好)
    拜谢日记
    拜谢cppomstar

    views counting

    Document

    Table of Contents