为什么有3个点TLE了?
查看原帖
为什么有3个点TLE了?
816549
52wyd楼主2023/4/11 20:19

为什么有3个点TLE了?

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

vector <int> a;
int res;

int merge_() {
	int k = 0;
	int sum = a[0] + a[1];
	
	for (int i = 1; i <= (int)(a.size()) - 2; i ++) {
		if (a[i] + a[i + 1] < sum) {
			sum = a[i] + a[i + 1];
			k = i;
		}
	}
	
	a.erase(a.begin() + k);
	a.erase(a.begin() + k);
	
	int idx = 0;
	for (int i = k - 1; i >= 0; i --) {
		if (a[i] > sum) {
			idx = i + 1;
			break;
		}
	}
	
	a.insert(a.begin() + idx, sum);
	return sum;
}

int main() {
	
	int n; n = read();
	
	for (int i = 1; i <= n; i ++)
	    a.push_back(read());

//	while (n --) {
//		a.push_back(read());
//	}
	
	int times = n - 1;
	while (times --) {
		res += merge_();
	}
	
	cout << res << endl;
	return 0;
}


2023/4/11 20:19
加载中...