一种神奇的做法但是可以拿95pt
查看原帖
一种神奇的做法但是可以拿95pt
590464
haogec123楼主2023/10/15 22:17

rt,WA on 20th

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
long long n,a[N]={0},b[N],c[N],p[N],b_sum[N],q;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
	for(int i=n;i>=1;i--)b_sum[i]=b_sum[i+1]+b[i];//反向的前缀和
  	 //所有数从1到0的最小值
	long long m1t0=9e18,pl;
	for(int i=n;i>=0;i--)
	{
		m1t0=min(m1t0,a[i]+b_sum[i+1]);
		if(b_sum[i]>m1t0)
		{
			pl=i;
			break;
		}
	}
	scanf("%lld",&q);
	while(q--)
	{
		int m;
		scanf("%lld",&m);
		for(int i=1;i<=m;i++)scanf("%lld",&p[i]);
		if(n<2000)//如果数据比较小就用暴力
		{
			long long price,min_p=9e18;
			for(int i=0;i<=n;i++)
			{
				price=a[i]+b_sum[i+1];//将数据分为两部分,前一部分用操作1,后半部分用操作2
				for(int j=1;j<=m;j++)
				{
					if(p[j]<=i)price+=c[p[j]];//操作3
					else price-=b[p[j]];//减去不必要的操作2
				}
				min_p=min(min_p,price);
			}
			printf("%lld\n",min_p);
		}
		else //速度比暴力快的错解
		{
			long long price,min_p=9e18;
			for(int i=pl;i<=n;i++)
			{
				price=a[i]+b_sum[i+1];
				for(int j=1;j<=m;j++)
				{
					if(p[j]<=i)price+=c[p[j]];
					else price-=b[p[j]];
				}
				min_p=min(min_p,price);
			}
			printf("%lld\n",min_p);
		}
	}
}

求调(错解可能不能调?)

2023/10/15 22:17
加载中...