社区讨论

为什么不会RE

P2120[ZJOI2007] 仓库建设参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo9n8g0g
此快照首次捕获于
2023/10/28 14:10
2 年前
此快照最后确认于
2023/10/28 14:10
2 年前
查看原帖
加上这句就 A 了,没加这句是 WA 不是 RE,为什么?
CPP
double Slope(int i, int j) 	{
	if (x(i) == x(j)) return INF;//加了这句就A了,防止除数是0 
	return (y(i) - y(j)) / ((x(i) - x(j)) * 1.0);
}
CPP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int nn = 1e6 + 10;
typedef long long LL;
const LL INF = 1e16;
int N;
LL F[nn], SumP[nn], SumT[nn];
LL X[nn], P[nn], C[nn];
int L, R, Q[nn];
LL x(int i) { return SumP[i]; }
LL y(int i) { return F[i] + SumT[i]; }
double Slope(int i, int j) 	{
	if (x(i) == x(j)) return INF;//加了这句就A了 
	return (y(i) - y(j)) / ((x(i) - x(j)) * 1.0);
}

int main () {
	ios::sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i ++) cin >> X[i] >> P[i] >> C[i];
	for (int i = 1; i <= N; i ++) {
		SumP[i] = SumP[i - 1] + P[i];
		SumT[i] = SumT[i - 1] + P[i] * X[i];
	}
	L = R = 1;
	for (int i = 1; i <= N; i ++) {
		while (L < R && Slope(Q[L], Q[L + 1]) <= X[i]) L++;
		F[i] = F[Q[L]] + X[i] * (SumP[i] - SumP[Q[L]]) - (SumT[i] - SumT[Q[L]]) + C[i];
		while (L < R && Slope(Q[R - 1], Q[R]) >= Slope(Q[R], i)) R--;
		Q[++R] = i;
	}
	LL Ans = F[N];
	for (int i = N; i >= 1; i --) {
		Ans = min (Ans, F[i]);
		if (P[i]) break;
	}
	cout << Ans;
}
/*
Val[j~i]=Sum[N]-Sum[j-1]-TOT[j~i]*X[i]
*/


回复

1 条回复,欢迎继续交流。

正在加载回复...