Problem

3/6

std::一意

Theory Click to read/hide

unique - 同一の連続要素のすべてのシーケンスを線形時間で 1 つに圧縮する関数。
引数として、圧縮を適用する必要がある配列の境界が渡されます。
反復子は、配列の新しい末尾 (両端を含まない) に返されます。新しい end の後で古い end の前にある要素には、未定義の値があるため注意が必要です。
詳しくはドキュメントをご覧ください。

ベクトルでこの関数を使用している場合は、返された結果を使用してサイズを変更すると便利です (詳細は後述)。

例:
  ベクトル a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; ユニーク (a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // unique 関数を使用すると便利です // 座標圧縮の補助配列 = { 235, 10, 41, 10, 41, 41, 235, 500, 500}; sort(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

Problem

このタスクの lower_bound 関数に慣れてください。

サイズ n の配列の座標を圧縮することは、相対的な順序を維持しながら、その要素を 0 から n-1 の整数にマッピングすることです。つまり、元の配列の任意の a と b について、次のことが当てはまります。 = b' < の場合b、次にa' < b' ただし、座標の圧縮により a が a' に変換される場合。そしてb to b'.

q 個のクエリが与えられ、クエリごとにサイズ ni の整数の配列が与えられ、その座標を圧縮して結果を出力する必要があります。

入力:
最初の行には、数値 q (1 <= q <= 20) - クエリの数が含まれます。
さらに、各リクエストに対して、最初に別の行で、数 ni (1 <= ni <= 5000) が指定されます -配列の場合、ni 整数、法は 109 を超えません - 配列要素。

出力:
クエリごとに、配列データ座標の圧縮結果を別の行に出力します。

例:
  <本体>
 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
入力 出力
2
5
300 -200 100 400 100
3
3 3 3 		2 0 1 3 1
0 0 0
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
// массив передается по ссылке
// поэтому он будет меняться и снаружи функции
void compress(vector<int>& arr) {
	vector<int> have = arr;     
for (int i = 0; i < arr.size(); i++)
		arr[i] =     
}
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int q;
	cin >> q;

	while (q--) {
		int n;
		cin >> n;

		vector<int> arr(n);
		for (int i = 0; i < n; i++)
			cin >> arr[i];

		compress(arr);
		for (int i = 0; i < n; i++)
			cout << arr[i] << ' ';
		cout << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!