Inversion Sequence

Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1555

Mean:

给你一个序列a[n]，要你按照要求去构造一个序列b。

序列a[i]表示序列b中的i前面有a[i]个数比i大。

转换一下就是：

已知一个连续的序列(1,2,3,4,...)，然后告诉了我们这个序列中每个数前面比本身大的个数，根据这些条件将这个序列调整顺序，找到满足条件的序列。

analyse:

STL大法好。直接用vector来insert。

Time complexity: O(nlogn)

Source code:

//  Memory   Time

//  1347K     0MS

//   by : crazyacking

//   2015-03-29-23.24

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstdlib>

#include<cstring>

#include<climits>

#include<iostream>

#include<algorithm>

#define MAXN 1000010

#define LL long long

using namespace std;

const int maxn = ;

int a[maxn];

int ans[maxn];

vector<int>v; 

int main(){

//    freopen("data.in","r",stdin);

    int n;

    while(scanf("%d",&n)!=EOF){

        for(int i=;i<n;i++){

            scanf("%d",&a[i]);

        }

        v.clear();

        v.push_back();

        int ok=;

        for(int i=n-;i>=;i--)

        {

            if(v.size()<=a[i])

            {

                ok=;

                break;

            }

            v.insert(v.begin()++a[i],i+);

//            for(int j=0;j<v.size();j++)

//                printf("%d%c",v[j],j==v.size()-1?'\n':' ');

        }

        if(ok){

            for(int i=;i<=n;i++){

                printf("%d%c",v[i],i==n?'\n':' ');

            }

        }else{

            puts("No solution");

        }

    }

    return ;

} 

/**************************************************************

    Problem: 1555

    User: crazyacking

    Language: C++

    Result: Accepted

    Time:164 ms

    Memory:1576 kb

****************************************************************/

巴特西

STL or 线段树 --- CSU 1555: Inversion Sequence

Inversion Sequence

Problem's Link: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1555

最新文章

热门文章