自看为O(N)复杂度却TLE60pts
查看原帖
自看为O(N)复杂度却TLE60pts
855522
youngsmart楼主2024/9/20 22:01
// fruit
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int num, id;
	bool f = false, lf = false;
} a[200010];

int main()
{
	// NO.4
	// n <= 1000可以使用暴力,和第三题一样做模拟,看似是O(n^2),但实际是O(n)(总共只需把n个数枚举完)预计得分100pts  
	ios::sync_with_stdio(0);
//	freopen("fruit.in", "r", stdin);
//	freopen("fruit.out", "w", stdout);
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].num), a[i].id = i;
	int t = n;
	a[0].num = -1;
	while (n > 0)
	{
		for (int i = 1; i <= t; i++)
		{
			if (a[i].f) continue;
			int last = i - 1;
			while (a[last].f && last > 0) last--;
			if (a[i].num != a[last].num)
			{
				printf("%d ", a[i].id);
				a[i].lf = true;
				n--;
			}
		}
		for (int i = 1; i <= t; i++) if (a[i].lf) a[i].f = a[i].lf;
		printf("\n");
	}
	return 0;
}
2024/9/20 22:01
加载中...