【Luogu3444】ORK-Ploughing（贪心）

题面

题解

我们知道，如果我们选定了以横向为主，或者纵向为主，

那么就有尽可能减少另一个方向上耕地的次数

所以分开贪心，但是本质相同，所以接下来只考虑纵向为主

既然确定了以纵向为主，那么就要尽可能减少横向操作的次数

所以，只要能够纵向耕地，就不考虑横向耕地

可是，如果到了某个时候，纵向无法耕了

此时必须横向耕

但是我们不知道应该从上面开始还是下面开始

为了解决这个问题

我们假设上面最多耕的次数是有限次

换种想法，我们假设上面至少耕这么多次

既然上面的次数确定，那么下方的耕地次数越少越好

所以耕地的优先级：

左-右-上-下

只要能够耕就一定耕

这样，枚举-贪心的做法就可以做啦

横向、纵向分别算一遍

时间复杂度O((n+m)^2)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 2222

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int K,m,n,ans=1e9;

int g[MAX][MAX];

int sl[MAX][MAX],sr[MAX][MAX];

int Work1(int up)

{

	int l1=1,l2=n,r1=1,r2=m,ret=0,ss;

	while(l1<=l2&&r1<=r2)

	{

		++ret;

		ss=sr[l2][r1]-sr[l1-1][r1];

		if(ss<=K){++r1;continue;}

		ss=sr[l2][r2]-sr[l1-1][r2];

		if(ss<=K){--r2;continue;}

		ss=sl[l1][r2]-sl[l1][r1-1];

		if(ss<=K&&l1<up){++l1;continue;}

		ss=sl[l2][r2]-sl[l2][r1-1];

		if(ss<=K){--l2;continue;}

		ret=1e9;break;

	}

	return ret;

}

int Work2(int left)

{

	int l1=1,l2=n,r1=1,r2=m,ret=0,ss;

	while(l1<=l2&&r1<=r2)

	{

		++ret;

		ss=sl[l1][r2]-sl[l1][r1-1];

		if(ss<=K){++l1;continue;}

		ss=sl[l2][r2]-sl[l2][r1-1];

		if(ss<=K){--l2;continue;}

		ss=sr[l2][r1]-sr[l1-1][r1];

		if(ss<=K&&r1<left){++r1;continue;}

		ss=sr[l2][r2]-sr[l1-1][r2];

		if(ss<=K){--r2;continue;}

		ret=1e9;break;

	}

	return ret;

}

int main()

{

	freopen("ork.in","r",stdin);

	freopen("ork.out","w",stdout);

	K=read();m=read();n=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			g[i][j]=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			sl[i][j]=sl[i][j-1]+g[i][j];

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			sr[i][j]=sr[i-1][j]+g[i][j];

	for(int i=1;i<=n;++i)

		ans=min(ans,Work1(i));

	for(int i=1;i<=m;++i)

		ans=min(ans,Work2(i));

	printf("%d\n",ans);

	return 0;

}

巴特西

【Luogu3444】ORK-Ploughing（贪心）

【Luogu3444】ORK-Ploughing（贪心）

题面

题解

最新文章

热门文章