40分TLE 求助大佬
查看原帖
40分TLE 求助大佬
538085
liysjianttso楼主2023/6/22 19:43

我的代码我分析的复杂度应该是O(n)(不过也有可能是我搞错了),但是它就是会TLE,请教一下,谢谢

(我的想法可能比较独特,蒟蒻说不清楚直接上图吧 临时画的比较丑 生动形象.jpg

#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;

int n;
struct con{//国家结构体
	int s,i;
	con(int a,int b){
		s = a,i = b;
	}
};
vector<con> v;
int main(){
	scanf("%d",&n);
	n = pow(2,n);
	for(int i = 1;i<=n;i++){
		int a;
		scanf("%d",&a);
		con c(a,i);
		v.push_back(c);//读入数据
	}
	while(v.size()>2){
		int d = 0;//这个变量下面几行再解释
		int now = v.size();
		for(int i = 0;i<now;i+=2){
			n = i-d;//因为下面一行删了元素之后size会变小 所以原来的第n个就变成了第n-1个(逻辑上应该没有什么问题)
			if(v[n].s>v[n+1].s)v.erase(v.begin()+n+1);
			d++;
		}
	}
	if(v[0].s>v[1].s){
		printf("%d",v[1].i);
	}
	else printf("%d",v[0].i);
	return 0;
}
2023/6/22 19:43
加载中...