Problem

3/6

标准::唯一

Theory Click to read/hide

unique - 一种在线性时间内将所有相同连续元素序列压缩为一个的函数。
作为参数，它传递数组的边界，在该边界内有必要应用压缩。
迭代器返回到数组的新末端（不包括）。您应该小心处理新结尾之后但旧结尾之前的元素，因为它们将具有未定义的值。
您可以在文档中阅读更多内容。

如果您在矢量上使用此函数，则可以方便地使用返回的结果调整大小（更多内容见下文）。

例子：
  矢量 a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; 独特的（a.begin（），a.end（））; // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // 使用 unique 函数做起来很方便 //坐标压缩辅助数组 a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; 排序（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，以下内容为真：如果 a = b，则 a' = b'如果一个 < b, 然后 a' < b'，前提是坐标的压缩把a变成a'和 b 到 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!