牛客练习赛44 A 小y的序列（模拟，细节）

链接：https://ac.nowcoder.com/acm/contest/634/A

来源：牛客网

小y的序列

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

Special Judge, 64bit IO Format: %lld

题目描述

小y有一块长度为n的布匹。颜色全部为0。他要给这个布匹染色。他总共有m种染料。小y认为一种染料用多次是不和谐的。所以每种染料会被用刚好一次。也就是说小y要给这块布匹染m次色。第i次会把L_iL

i

到R_iR

i

这个区间染成颜色i。现在给出最终布匹每段的颜色。请你输出一种染色方案。数据保证有解

输入描述:

输入共两行。

第一行两个个正整数n,m，表示布匹的长度和染料的数量

第二行n个用空格隔开的正整数，第i个数字a_ia

i

表示第i个布匹的颜色。

输出描述:

输出m行。

第i行包含两个正整数L_i,R_iL

i

,R

i

,表示第i次染色的区间。

示例1

输入

复制

3 3

1 2 3

输出

复制

1 3

2 3

3 3

备注:

1 \leq n ,m\leq 10^51≤n,m≤10

5

0 \leq a_i \leq m0≤a

i

≤m

1\le L_i \le R_i\le n1≤L

i

≤R

i

≤n

思路：

本题细节过多，需要仔细读题。

我们用两个数组 l[i] ,r[i] 分别代表颜色i出现的最左位置和最右位置，

如果这个颜色在最终数组中没有出现，那么一定是被编号比它大的颜色覆盖掉了，

那么对于没有出现的颜色，我们就输出出现过的编号最大的颜色所在的位置即可。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int l[maxn];

int r[maxn];

int n;

int m;

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    cin>>n>>m;

    repd(i,1,m)

    {

        l[i]=inf;

    }

    int x;

    int ok;

    repd(i,1,n)

    {

        cin>>x;

        l[x]=min(l[x],i);

        r[x]=max(r[x],i);

    }

    for(int i=m;i>=1;i--)

    {

        if(l[i]!=inf)

        {

            ok=l[i];

            break;

        }

    }

    repd(i,1,m)

    {

        // cout<<i<<endl;

        if(l[i]==inf)

        {

            cout<<ok<<" "<<ok<<endl;

            continue;

        }

        // cout<<endl;

        cout<<l[i]<<" "<<r[i]<<endl;

    }

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

牛客练习赛44 A 小y的序列（模拟，细节）

最新文章

热门文章

巴特西

牛客练习赛44 A 小y的序列 （模拟，细节）

最新文章

热门文章

牛客练习赛44 A 小y的序列（模拟，细节）