社区讨论

萌新求助斜率优化入门题

HHaber
P4360[CEOI 2004] 锯木厂选址参与者 3已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@lo85npf9
此快照首次捕获于
2023/10/27 13:10
2 年前
此快照最后确认于
2023/10/27 13:10
2 年前
查看原帖
喜提 2828 Pts.
和题解拍了 19701970 组数据之后，发现了这个能 Hack 掉我代码的数据：
CPP
6
1 6
1 0
1 0
1 4
1 0
6 4
Answer:
CPP
6
My code:
CPP
12
然后你会发现：如果把第二个判断斜率的地方改成 <<，那么答案就正确了！然而交上去只有 5858 Pts.
然后，又改成 << 和题解拍，拍了大概 12001200 组之后，又出现了一个能 Hack 掉改后的代码，数据：
CPP
8
1 0
1 0
1 8
2 0
4 0
8 6
6 8
2 0
Answer:
CPP
24
My code:
CPP
48
然后你会惊人地发现，如果我把 << 改回 >>，那么答案就正确了！
显然我已经想到了一种可以非法 AC 本题的方法，但是我还是想求助一下诸位大佬帮我调一下。
思路见 这个帖。
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,ans=2e18;
const int N=2e4+4;
long long f[N];
long long tot;
long long dis[N],weight[N];
long long head=1,tail=1;
long long q[N],d[N],w[N];
long long sq(long long i){
	return weight[i]*dis[i];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>d[i];
		dis[i+1]=dis[i]+d[i];	//Before i this point.
		weight[i]=weight[i-1]+w[i];
	}
	for(int i=1;i<=n;i++) tot+=(dis[n+1]-dis[i])*w[i];
	for(int i=1;i<=n;i++){
		while(head<tail&&sq(q[head+1])-sq(q[head])<dis[i]*(weight[q[head+1]]-weight[q[head]])) head++;
		f[i]=tot-weight[q[head]]*(dis[n+1]-dis[q[head]])-(weight[i]-weight[q[head]])*(dis[n+1]-dis[i]);
		while(head<tail&&(sq(i)-sq(q[tail]))*(weight[q[tail]]-weight[q[tail-1]])>(sq(q[tail])-sq(q[tail-1])*(weight[i]-weight[q[tail]]))) tail--;	//大于小于问题 
		q[++tail]=i;
	}
	for(int i=1;i<=n;i++) ans=min(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}
关注会给，放心。

回复

共 3 条回复，欢迎继续交流。

正在加载回复...