求助双指针
查看原帖
求助双指针
231946
CuSO4_and_5H2O楼主2022/10/20 08:51

RT,代码敲出来之后,发现

#include<bits/stdc++.h>
#define int long long
#define max(A,B) (A<B?B:A)
#define min(A,B) (A>B?B:A)
#define bug cout<<"I AK IOI"<<endl;
#define gc getchar
using namespace std;
const int N=507;

inline void print(int x) {if (x < 0) putchar('-'), x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0');}
inline int read(){int res = 0, f = 0; char ch = gc();for(; !isdigit(ch); ch = gc()) f |= (ch == '-'); for(;isdigit(ch);ch=gc()) res = (res << 1) + (res << 3) + (ch ^ '0');return f ? -res :res;}

int n,m,A,B;
int a[N][N],lie[N][N],qj[N];
int l,ans=1e18;

signed main(){
	n=read(),m=read(),A=read(),B=read();
	if(A>B) swap(A,B);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
			lie[j][i]=lie[j][i-1]+a[i][j];
		}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			for(int k=1;k<=m;k++) qj[k]=lie[k][i]-lie[k][j-1]+qj[k-1];
			l=1;
			for(int r=1;r<=m;r++)
			{
				while(l<r && B<qj[r]-qj[l-1]) l++;
				ans=min(ans,abs(qj[r]-qj[l-1]-A)+abs(qj[r]-qj[l-1]-B));
				if(l >= 2) ans = min(ans, abs(qj[r]-qj[l-2]-A)+abs(qj[r]-qj[l-2]-B));
			}
		}
	}
	cout<<ans;
}

如果注释掉if(l >= 2) ans = min(ans, abs(qj[r]-qj[l-2]-A)+abs(qj[r]-qj[l-2]-B));会WA4个,为什么??看了所有题解,没有说这个问题的,如果有相关博客,请发出来然后我紫衫

2022/10/20 08:51
加载中...