【悬关】斜率优化 WA 90pts 求调
查看原帖
【悬关】斜率优化 WA 90pts 求调
767765
Arson1st楼主2024/1/2 19:13

WA on #2,代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4+10;

int n, stk[N], top, q[N], h = 1, t = 1;
long long f[N];
struct node{
	int w, l;
} p[N];

bool cmp(node x, node y) {
	if (x.w == y.w) return x.l < y.l;
	return x.w < y.w;
}

double K(int a, int b) {
	return 1.0 * (f[b] - f[a]) / (p[stk[a+1]].l - p[stk[b+1]].l);
} //计算斜率

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%lld%lld", &p[i].w, &p[i].l);
	sort(p+1, p+n+1, cmp);
	for (int i = 1; i <= n; i ++) {
		while (top && p[i].l > p[stk[top]].l) top --;
		stk[++ top] = i;
	} //维护有用土地的单调栈
	for (int i = 1; i <= top; i ++) {
		while (h < t && K(q[h], q[h+1]) <= p[stk[i]].w) h ++;
		f[i] = f[q[h]] + p[stk[i]].w * p[stk[q[h]+1]].l;
		while (h < t && K(q[t-1], q[t]) >= K(q[t], i)) t --;
		q[++ t] = i;
	} //斜率优化,已压入0节点
	printf("%lld", f[top]);
} 
2024/1/2 19:13
加载中...