Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2095-d8f46564
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #75 DIV1 B問題/DIV2 D問題 - Queue (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 B問題 (1000pt)
Codeforces Beta Round #72 DIV2 D問題 (2000pt)
Problem description

問題概要

N要素 (10^5以下) の整数列が与えられる.
各要素に対して,自分より厳密に小さい要素で,自分より右にある要素で,最も右にある要素までの距離-1を求める問題.
そのような要素が存在しないなら-1を返す.

解法

数列を小さい順にソートする.同じ大きさなら元々左にあったものが先に来るようにする.
後は,最初から見てやって,もともといた位置の最も右の位置を覚えておいて,そこまでの距離を返す.

C++言語のスパゲッティなコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int in[120000], res[120000];
pair<int,int> s[120000];

int main(){
  int i,j,k,l,m,n;
  int mx;

  while(scanf("%d",&n)==1){
    rep(i,n) scanf("%d",in+i);
    rep(i,n) s[i].first = in[i], s[i].second = i;
    sort(s,s+n);

    mx = -1;
    rep(i,n){
      if(mx < s[i].second) mx = s[i].second;
      res[s[i].second] = mx - s[i].second - 1;
    }

    rep(i,n){
      if(i) putchar(' ');
      printf("%d",res[i]);
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2095-d8f46564
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。