50pts WA 代码简洁,求调
查看原帖
50pts WA 代码简洁,求调
396994
Winston12321_楼主2023/7/1 21:00

本人没看出来问题。。。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n;
struct land{
	long long w,h;
}l[50010],z[50010],la;
int cnt;
bool cmp(land x1,land x2)
{
	if(x1.w==x2.w) return x1.h>x2.h;
	else return x1.w>x2.w;
}
long long dp[50010];
queue<int>Q;
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i) cin>>l[i].w>>l[i].h;
	sort(l+1,l+n+1,cmp);
	for(int i=1;i<=n;++i)
		if(l[i].h>la.h)
			la=l[i],z[++cnt]=l[i],dp[cnt]=600000000000000000;
	Q.push(0);
	for(int i=1;i<=cnt;++i)
	{
		int fr=Q.front();
		dp[i]=dp[fr]+z[fr+1].w*z[i].h;
		if(i<cnt) while(dp[i]-dp[fr]<=z[i+1].h*(z[fr+1].w-z[i+1].w) && !Q.empty()) Q.pop(),fr=Q.front();
		Q.push(i);
	}
	cout<<dp[cnt]<<endl;
	return 0;
}
2023/7/1 21:00
加载中...