题解 P1086 【花生采摘】

· · 题解

这道题其实有点坑

我不会告诉你我做了一个小时

首先，这道题化简一下就是说去从大到小依次采摘花生，

那我们只要记录每株花生的位置和数量，快排一遍就可以了。

然后第X大的花生和第Y大的花生的距离其实就是

abs(x_x-x_y)+(y_x-y_y)

图画一下就可以发现了。

整理一下，那么这个代码就是O(k)的时间复杂度了

代码实现

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
inline int read()//快读 
{
    int x=0;char s=getchar();
    while(s>'9'||s<'0') s=getchar();
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x; 
}
struct node
{
    int x,y,sum;
}a[401];
int m,n,k,ans,maxx,nm=1;
bool cmp(const node &x,const node &y)
{
    return x.sum>y.sum;
}
int main()
{
    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++,nm++)
    {
        a[nm].sum=read();
        a[nm].x=i;
        a[nm].y=j;
    }
    sort(a+1,a+nm,cmp);//快排 
    int len=1;
    k-=a[len].x;
    while(k>0)
    {
        k--;
        ans+=a[len].sum;
        if(k>=a[len].x)
            maxx=maxx<ans?ans:maxx;
        len++;
        if(len>nm)
            break;
        /*
        从一个点到另一个点的算法 
        */ 
        int num1=a[len].x-a[len-1].x;
        int num2=a[len].y-a[len-1].y;
        if(num1<0)
            num1=-num1;
        if(num2<0)
            num2=-num2;
        k-=num2+num1;
    }
    printf("%d\n",maxx);
    return 0;
}