Problem

3/6

std::benzersiz

Theory Click to read/hide

benzersiz - aynı ardışık öğelerin tüm dizilerini doğrusal zamanda bire sıkıştıran bir işlev.
Argüman olarak, içinde sıkıştırma uygulanması gereken dizinin sınırları iletilir.
Dizinin yeni sonuna (dahil değil) bir yineleyici döndürülür. Tanımsız bir değere sahip olacağından, yeni sondan sonra eskisinden önceki öğelere dikkat etmelisiniz.
Daha fazla bilgiyi belgelerde okuyabilirsiniz.

Bu işlevi bir vektör üzerinde kullanıyorsanız, döndürülen sonucu kullanarak yeniden boyutlandırmak uygundur (bununla ilgili daha fazlası aşağıda).

Örnekler:
  vektör a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; unique(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // benzersiz işlevi kullanmak uygundur // koordinat sıkıştırma için yardımcı dizi bir = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // bir = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(benzersiz(a.begin(), a.end()) - a.begin()); // bir = [10, 41, 235, 500]  

Problem

Bu görev için lower_bound işlevini öğrenin.

n boyutunda bir dizinin koordinatlarını sıkıştırmak, elemanlarının 0'dan n-1'e kadar olan tamsayılara göreli sırayı koruyarak eşlenmesidir. Yani, orijinal dizideki herhangi bir a ve b için şu doğrudur: a = b ise, o zaman a' = b' ve eğer bir < b, ardından a' < b', koordinatların sıkıştırılmasının a'yı a''ya dönüştürmesi şartıyla ve b'den b''ye.

Size q sorguları verildi, burada her sorgu için size ni boyutunda bir tamsayı dizisi verildi ve sizin koordinatlarını sıkıştırmanız ve sonucu yazdırmanız gerekiyor.

Giriş:
İlk satır q (1 <= q <= 20) sayısını içerir - sorgu sayısı.
Ayrıca her istek için önce ayrı bir satırda ni (1 <= ni <= 5000) sayısı verilir - boyutu dizi, daha sonra ni tamsayı olarak verilir, modulo 10'u geçmeyen9 - dizi elemanları.

Çıktı:
Her sorgu için dizi veri koordinatlarının sıkıştırma sonucunu ayrı bir satıra yazdırın.

Örnekler:
 
 

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++
Giriş Çıktı
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!