[Codeforces]1398D – Rearrange
本文最后更新于 161 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/cf1398d/

题意

给一个矩阵,其中元素值遍历 $1,2,\ldots,n \times m$,定义 $X$ 为每行最大值构成的集合,$Y$ 为每列最大值构成的集合,要求构造一个矩阵,使得:
$X$ 与原矩阵 $X$ 相同,$Y$ 与原矩阵 $Y$ 相同,且每行、每列都是单峰的。

解法

首先注意的是, $X$ $Y$ 是集合,说明可以无视顺序。
如何构造能够单峰呢?考虑从大到小填数,这样每填一个数就能确定行列最大值。
设当前枚举的数为 $num$,设前方有 $x$ 行的最大值 $\ge num$,$y$ 列的最大值 $\ge num$。
由于 $num$ 单调递减,因此 $x$ $y$ 单调递增。
如果 $num$ 是最大值的话,将 $num$ 填在 $(x,y)$ 的位置即可保证在此处取到,因为比 $num$ 大的全在前面,而后面填的数一定比 $num$ 小。
如果 $num$ 不是最大值,说明 $num$ 一定被前面的 $num$ 覆盖了,填在前方被覆盖位置即可。
用队列保存一下被覆盖位置,根据先进先出原则,从最靠近的到最远离的入队,即可保证从靠近到远离递减。
那么最大值前方单调递增已经保证了,还需要保证最大值后方单调递减。显然 $num$ 从大到小,而填数由近及远,这个也是可以保证的。

#include <cstdio>
#include <queue>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 300;
int n,m;
int r[maxn],c[maxn];
int a[maxn][maxn];
queue<pair<int,int> > q;
int main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j)
    {
        int x;
        read(x),r[i] = std::max(r[i],x),c[j] = std::max(c[j],x);
    }
    sort(r + 1,r + 1 + n),sort(c + 1,c + 1 + m);
    int x = 0,y = 0,i = n,j = m; 
    for(int num = n * m;num;--num)
    {
        if(r[i] == num) ++x;
        if(c[j] == num) ++y;
        if(r[i] == num || c[j] == num) a[x][y] = num;
        else a[q.front().first][q.front().second] = num,q.pop();
        if(r[i] == num)
        {
            //num is max in row i,so positions before it is ok
            for(int k = y - 1;k > 0;--k) q.push(make_pair(x,k));
            --i;
        }
        if(c[j] == num)
        {
            for(int k = x - 1;k > 0;--k) q.push(make_pair(k,y));
            --j;
        }
    }
    for(int i = 1;i<=n;putchar('\n'),++i) for(int j = 1;j<=m;++j) printf("%d ",a[i][j]);
    return 0;
}
本文标题:[Codeforces]1398D – Rearrange
本文作者:Clouder
本文链接: https://www.codein.icu/cf1398d/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇