基础算法----离散化 unique STL

本文主要是介绍基础算法----离散化 unique STL，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

离散化

1、排序

2、对排序后的数据去重(可以使用unique)，同时用1-m的数字和新数组储存；

void discret()
{
	sort(a + 1, a + 1 + n);
	int tot = 0;
	For(i, i, n)
	{
		if(i == 1 || a[i] != a[i-1])
			uni[++tot] = a[i];
	}
}

3、查询

int find(int x)
{
    return lower_bound(uni + 1, uni + 1 + totu, x) - uni;
}

例aw103电影

题目链接：AcWing 103. 电影--离散化的应用 - AcWing

离散化，但不能忘记无解的情况！！

//#pragma comment(linker,   "/STACK:10240000000000,10240000000000")
//#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define For(i,a,b) for (int i=(a);i<=(b);++i)
#define Fod(i,b,a) for (int i=(b);i>=(a);--i)
#define mls multiset
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define itt iterator
#define clr(x) memset(x, 0, sizeof(x));

typedef long long ll;
typedef unsigned long long ull;
		
using namespace std;
const int MAXN = 0x7fffffff;
const int N = 2e5 + 50;

int lang[3*N];
int uni[3*N];
int a[N];
int b[N];
int c[N];
int ans[3*N];
int n, m;

int totl;
int totu;

int find(int x)
{
	return lb(uni + 1, uni + totu + 1, x) - uni;
}

int main ()
{	
	cin >> n;
	For(i, 1, n)
	{
		cin >> a[i];
		lang[++totl] = a[i];
	}
	cin >> m;
	For(i, 1, m)
	{
		cin >> b[i];
		lang[++totl] = b[i];
	}
	For(i, 1, m)
	{
		cin >> c[i];
		lang[++totl] = c[i];
	}

	sort(lang + 1, lang + 1 + totl);
	//unique()大法
	// auto new_end = unique(lang + 1, lang + 1 + totl);
	// totu = new_end - lang;
	// For(i, 1, totu) uni[i] = lang[i];
	For(i, 1, totl)
	{
		if(i == 1 || lang[i] != lang[i-1])
			uni[++totu] = lang[i];
	}

	For(i, 1, n) ans[find(a[i])]++;
	
	int anss = 0;
	int bmax = 0, cmax = 0;
	For(i, 1, m)
	{
		int x = find(b[i]);
		int y = find(c[i]);
		if(ans[x] > bmax || (ans[x] == bmax && ans[y] > cmax))
		{
			bmax = ans[x];
			cmax = ans[y];
			anss = i;
		}
	}
	if(anss != 0) cout << anss << endl;
	else cout << 1 << endl;
	return 0;
}	
/*

*/

这篇关于基础算法----离散化 unique STL的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！