前言

2s 时间完全没必要，1s 即可做好了，平方算法加退火也让别人拿到满分，没有一个超时 hack 数据，这让我们

O(n)

的人怎么办。按道理讲我的算法时严格为

O(n)

的后面加 hack 数据应该不会让我错。

思路

一道贪心题。

由于

f_i

是单调不降的，则对于一个为如：

CPP

2 3 4 4 3 2

的数据坑定是取 4 4 时答案为最小，否则取如 3 4 4 3 时 4 4 被更大的

f_i

求值了。

这样就如括号一样，如 ((()))(()) ，只要取并列括号中最中间最小的即可。 ((())) 中，只需要取最中间的括号即可。

由此只要用栈来找最中间的括号，然后求值取最小即可。

不懂看代码注释吧。

CODE

CPP

int n, i;
int a[1000100], e[1000100], pos[1000100];
LL val[1000100], f[1000100];
bool h[1000100];
LL mi = 1e18;
int top;
int stk[1000100], id[1000100];
void get(int l, int r) {
	LL ans = 0;
	for (int i = l; i <= r; ++i)
		ans += val[i] * f[i - l + 1];
	mi = min(mi, ans);
}
int main () {
	n = read();
	for (i = 1; i <= n; ++i) a[i] = read();
	for (i = 1; i <= n; ++i) val[i] = 1ll * read(), ++e[a[i]], h[a[i]] = 1; // e保存数量 
	for (i = 1; i <= n; ++i) f[i] = 1ll * read();
	
	for (i = 1; i <= n; ++i) {
		int x = a[i];
		if(h[x] == 1) //h为是否在此之前加入过栈中 
			pos[x] = i, h[x] = 0; //pos记录最早出现的位置 
			
		stk[++top] = x; id[top] = i; --e[x]; //入栈 
		
		bool flag = false;
		while(top > 0 && e[stk[top]] == 0) //全部如栈了弹出 
			--top, flag = true; //括号匹配成功才做后面 
			
		if(flag && e[stk[top + 1]] == 0 && pos[stk[top + 1]] == id[top + 1]) { // 这一种类结束，且已经全部弹完，求值 
			get(id[top + 1], i); //求答案 
			top = 0; //贪心，((()))只要取最中间的即可剩下外边的直接弹出栈 
		}
		
	}
	printf("%lld", mi);
}

题解：P14567 【MX-S12-T2】区间

文章操作

前言

思路

CODE

相关推荐

评论

题解：P14567 【MX-S12-T2】区间