求助玄学问题
  • 板块灌水区
  • 楼主Kingna
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/6/30 21:35
  • 上次更新2023/10/27 22:12:14
查看原帖
求助玄学问题
411727
Kingna楼主2022/6/30 21:35

这是某道题的TLE代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	char c = ' ';
	int f = 1, x = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void wr(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}


const int N = 2e5 + 5;
int t, n, k;
int a[N];
vector<int> gg;

int main() {
	cin >> t;
	while (t--) {
		gg.clear();
		unordered_map<int, int> g;   //区别 
		n = read(), k = read();
		for (int i = 1; i <= n; i++) a[i] = read(), g[a[i]]++;
		int maxn = 0, id = 0;
		for (auto i = g.begin(); i != g.end(); i++) {
			if (i -> second >= k) {
				gg.push_back(i -> first);
			}
	
		}
		if (gg.size() == 0) {
			puts("-1");
			continue;
		}
		sort(gg.begin(), gg.end());
		int l = gg[0], r = gg[0], st = gg[0];
		for (int i = 1; i < gg.size(); i++) {
			if (gg[i] == gg[i - 1] + 1) {
				if (maxn < gg[i] - st) {
					maxn = gg[i] - st;
					l = st, r = gg[i];
				}
			}
			else {
				st = gg[i];
			}
		}
		wr(l);
		putchar(' ');
		wr(r);
		putchar('\n');
	}
}

然后这份代码是AC代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	char c = ' ';
	int f = 1, x = 0;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void wr(int x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) wr(x / 10);
	putchar(x % 10 + '0');
}


const int N = 2e5 + 5;
int t, n, k;
int a[N];
vector<int> gg;

int main() {
	cin >> t;
	while (t--) {
		gg.clear();
		map<int, int> g;   //区别 
		n = read(), k = read();
		for (int i = 1; i <= n; i++) a[i] = read(), g[a[i]]++;
		int maxn = 0, id = 0;
		for (auto i = g.begin(); i != g.end(); i++) {
			if (i -> second >= k) {
				gg.push_back(i -> first);
			}
	
		}
		if (gg.size() == 0) {
			puts("-1");
			continue;
		}
		sort(gg.begin(), gg.end());
		int l = gg[0], r = gg[0], st = gg[0];
		for (int i = 1; i < gg.size(); i++) {
			if (gg[i] == gg[i - 1] + 1) {
				if (maxn < gg[i] - st) {
					maxn = gg[i] - st;
					l = st, r = gg[i];
				}
			}
			else {
				st = gg[i];
			}
		}
		wr(l);
		putchar(' ');
		wr(r);
		putchar('\n');
	}
}

两份代码区别只有 unordered_map 改成了 map ,按理来说应该变慢,但是为什么AC了

2022/6/30 21:35
加载中...