codeforce 379 C New Year Ratings Change問題解

タイトル接続:http://codeforces.com/problemset/problem/379/C
重複値を持つ数列Aを重複値のない新しい数列Bにするには、新しい数列の総和がすべての実行可能解の中で最も小さく、新しい数列のいずれの値もA数列の対応する値より小さくてはならないことが要求される.
考え方:
1まずA数列を並べ替え、pair、またはカスタムstuctを使用して、数値と下付きの対応関係を記録する
2次にA数列の最小値からB数列に記入し、最初の最小値は直接Bに記入すればよい.
3それからA数列の現在の値と前の記入値を比較して、大きい値をB数列に記入します.
4記録された下付き文字を利用して、B数列に記入する必要がある位置をすばやく位置決めすることができます.

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

const int MAX_N = (int)3E5+1;

pair<int,int> arr[MAX_N];
int a2[MAX_N];

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i].first);
		arr[i].second = i;
	}
	sort(arr, arr+n);
	int c = arr[0].first;
	a2[arr[0].second] = c;

	for (int i = 1; i < n; i++)
	{
		if (arr[i].first <= c) a2[arr[i].second] = ++c;
		else a2[arr[i].second] = (c = arr[i].first);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a2[i]);
	}
	return 0;
}