首页 > 试题广场 >

采花生

[编程题]采花生
  • 热度指数:12716 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 16M,其他语言32M
  • 算法知识视频讲解
鲁宾逊先生有一只宠物猴,名叫多多。这天,他们两个正沿着乡间小路散步,突然发现路边的告示牌上贴着一张小小的纸条:“欢迎免费品尝我种的花生!——熊字”。
鲁宾逊先生和多多都很开心,因为花生正是他们的最爱。在告示牌背后,路边真的有一块花生田,花生植株整齐地排列成矩形网格。有经验的多多一眼就能看出,每棵花生植株下的花生有多少。为了训练多多的算术,鲁宾逊先生说:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件:
1. 从路边跳到最靠近路边(即第一行)的某棵花生植株;
2. 从一棵植株跳到前后左右与之相邻的另一棵植株;
3. 采摘一棵植株下的花生;
4. 从最靠近路边(即第一行)的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布,请问在限定时间内,多多最多可以采到多少个花生?
注意可能只有部分植株下面长有花生,假设这些植株下的花生个数各不相同。例如花生田里只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生,个数分别为 13, 7, 15, 9。多多在 21 个单位时间内,只能经过(4, 2)、(2, 5)、(5, 4),最多可以采到 37 个花生。

输入描述:
输入包含多组数据,每组数据第一行包括三个整数 M(1≤M≤20)、N(1≤N≤20)和 K(0≤K≤1000),用空格隔开;表示花生田的大小为 M * N,多多采花生的限定时间为 K个单位时间。
紧接着 M 行,每行包括 N 个自然数 P(0≤P≤500),用空格隔开;表示花生田里植株下花生的数目,并且除了0(没有花生),其他所有植株下花生的数目都不相同。


输出描述:
对应每一组数据,输出一个整数,即在限定时间内,多多最多可以采到花生的个数。
示例1

输入

6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

输出

37
啥头像
总体思路:
        1.存储花生信息,按照数量排序。可以用一个Peanut类来表征
        2.对1中有花生的植株,计算 “到那儿”+“采花生”+“回来”的时间是否小于剩余的时间,若是,则可以去,否组结束。并累加能采到的花生。

代码如下:
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Peanut
{
    int x, y, amount;
    Peanut(int _x, int _y, int _amount) {
        x = _x; y = _y; amount = _amount;
    }
    bool operator<(const Peanut& that) const {
        return (amount>that.amount);
    }
};

int main()
{
    // 输入
    int M, N, K;
    int tempAmount, tempX, tempY, dist, rlt;
    while(~scanf("%d %d %d", &M, &N, &K)) {
        vector<Peanut> peanut;
        for(int i=1; i<=M; i++) {
            for(int j=1; j<=N; j++) {
                scanf("%d", &tempAmount);
                if(tempAmount) {
                    peanut.push_back(Peanut(i, j, tempAmount));
                }
            }
        }
        sort(peanut.begin(), peanut.end());

        // 计算
        rlt = 0;
        if(peanut.size()) {
            tempY = peanut[0].y; tempX = 0;
            for(int i=0; i<peanut.size(); i++) {
                dist = abs(tempX-peanut[i].x) + abs(tempY-peanut[i].y)+1;
                if(K >= dist + peanut[i].x) {
                    K -= dist;
                    tempX = peanut[i].x;
                    tempY = peanut[i].y;
                    rlt += peanut[i].amount;
                } else {
                    break;
                }
            }
        }

        // 输出
        printf("%d\n", rlt);
    }
    return 0;
} 


发表于 2016-01-03 17:14:13 回复(4)


这道题并不复杂,但是题目要求容易被忽略,导致有个别测试用例无法通过。
==先注意以下几点:==

1、花生采摘顺序是从多到少的植株,因此需要对所有花生植株进行排序!
    假设花生植株a>b>c>d>e,你的采摘顺序必须是a、b、c、d、e,不能打乱!!!
    别TM和我一样自作聪明,采取类贪心策略,选取最优路径采摘最多的花生。。。

2、转去采摘某颗花生时,必须要考虑剩下的时间能不能采摘到花生并且回到路边。
    转去目标需要的时间 + 采摘花生需要的时间 + 回到路边的时间

3、初始状态在路边,去第一行任意一列的时间都是1个单位时间!!!
    题目中明确说了!!!别问为什么。。。

4、示意图:
  列数  ①  ②  ③  ④  ⑤  ⑥  ⑦
第0行 |  路-----------边
第1行 | 0  0  0  0  0  0  0
第2行 | 0  0  0  0  13 0  0
第3行 | 0  0  0  0  0  0  7
第4行 | 0  15 0  0  0  0  0
第5行 | 0  0  0  9  0  0  0

5、任意节点(row, col)回到路边,需要row个单位时间!!!

#include <iostream>
(720)#include <math.h>
using namespace std;

struct Node {
    //花生所处行、列,花生数
    int row;
    int col;
    int count;

    Node() {
        this->row = 0;
        this->col = 0;
        this->count = 0;
    }

    Node(int row, int col, int count) {
        this->row = row;
        this->col = col;
        this->count = count;
    }
};

// 希尔排序:按照count化生数降序排列
void sort(Node* nodes, int size) {
    //初始步长为数组长度的一般
    int d = size / 2;
    Node temp(0, 0, 0);
    while (d > 0) {
        for (int i = d; i < size; ++i) {
            int j = i;
            while (j >= d && nodes[j].count > nodes[j - d].count) {
                //交换nodes[j]、nodes[j - d]
                temp = nodes[j];
                nodes[j] = nodes[j - d];
                nodes[j - d] = temp;
                j -= d;
            }
        }
        //缩小步长
        d /= 2;
    }
}

int main(int argc, const char* argv[]) {
    int m = 0, n = 0, k = 0;
    Node nodes[400] = {};
    //scanf返回值为正确输入数据的变量个数,当一个变量都没有成功获取数据时,此时返回-1
    while (scanf("%d %d %d", &m, &n, &k) != -1) {
        int tempP = 0;
        //第一步:获取输出二维数组信息
        for (int row = 1; row <= m; ++row) {
            for (int col = 1; col <= n; ++col) {
                //将二维数组输入转为一维数组,方便进行排序
                nodes[(row - 1) * n + col - 1].row = row;
                nodes[(row - 1) * n + col - 1].col = col;
                scanf("%d", &tempP);
                nodes[(row - 1) * n + col - 1].count = tempP;
            }
        }
        //第二步:按照花生数降序排列
        sort(nodes, m * n);
        //第三步:按照花生植株所含花生数从大->小的顺序采摘
        //nowRow、nowCol记录当前所处位置,初始为(0, nodes[0].col),是因为根据模型知,路边处于第0行,并且路边到第一行只需要1个单位时间,所以可以到任意列
        int resCount = 0, nowRow = 0, nowCol = nodes[0].col, nextK;
        for (int i = 0; i < m * n; ++i) {
            //nextK记录从(nowRow, nowCol)转移到nodes[i]需要的步骤数,以及采摘花生需要1单位时间
            nextK = abs(nodes[i].row - nowRow) + abs(nodes[i].col - nowCol) + 1;
            if (nextK + nodes[i].row > k) {
                //由于采完花生需要回到路边,因此剩下的k必须够采花生,并且回到路边需要nodes[i].row单位时间
                break;
            }
            //转移到nodes[i]
            k -= nextK;
            nowRow = nodes[i].row;
            nowCol = nodes[i].col;
            resCount += nodes[i].count;
        }
        printf("%d\n", resCount);
    }
    return 0;
}
————————————————
版权声明:本文为CSDN博主「hestyle」的原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://hestyle.blog.csdn.net/article/details/104686298
发表于 2020-03-05 23:04:07 回复(0)

这个题很坑,因为描述不清楚,前面的评论写的人描述的也不是很清楚,我这里把有坑的地方给大家说明一下:

  1. 输入是要循环输入的,不是只有一组用例,有很多组,如果输入一组用例退出的话会报错,具体可以参考我的程序
  2. 这个题的意思是,从路边到第一个花生不用算列的时间,直接从第0行到第n行(第一个花生所在的行数),用n的时间,采摘+1时间,然后到下一个花生,不会返回路边,只有到最后一个花生才会返回路边

PS:统一回复一下前面栈溢出,输出错误例子不明确的同学,牛客网的例子输出好像有bug,一般这种情况都是你们程序写错了,不妨就认为没有错误用例输出重新改程序把,当acmer

/*
 * =====================================================================================
 *
 *       Filename:  1001.cpp
 *
 *    Description:  PAT乙级练习题:1001采花生
 *
 *        Version:  1.0
 *        Created:  2018/04/30 19:03:37
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:   Zhangxin
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include<iostream>
#include<cmath>
#include <algorithm>
#include<vector>
using namespace std;

struct Penut {
    int row;
    int col;
    int value;
};                /* ----------  end of struct Penut  ---------- */
bool cmp(Penut a,Penut b) {
    return a.value>b.value;
}


typedef struct Penut Penut;

#include    <stdlib.h>

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
int main ( int argc, char *argv[] ) {
    freopen("data.in","r",stdin);
    int m,n,k,r,c,v;
    while(scanf("%d %d %d",&m,&n,&k)==3) {
        vector<Penut> ps;
        Penut a;
        a.row=0;
        a.col=1;
        a.value=100000;
        ps.push_back(a);
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                scanf("%d",&v);
                if(v!=0) {
                    Penut p;
                    p.row=i;
                    p.col=j;
                    p.value=v;
                    ps.push_back(p);
                    //             cout<<"input "<<v<<endl;
                }

            }
        }
        sort(ps.begin(),ps.end(),cmp);
        ps[0].col=ps[1].col;
      //  for(vector<Penut>::iterator i=ps.begin(); i!=ps.end(); i++) {
      //      printf("%d ",i->value);
      //  }
      //  cout<<endl;
        int time=0;
        int res=0;
        int index=1;
        while(time<k && index<ps.size()) {
            //  cout<<index<<endl;
            int temp=abs(ps[index].col-ps[index-1].col)+abs(ps[index].row-ps[index-1].row)+1;
        //    cout<<index<<" "<<time<<" "<<temp<<" "<<temp+time+ps[index].row<<endl;
            if(temp+time+ps[index].row<=k) {
                time=time+temp;
                //  cout<<index<<" "<<res<<" "<<temp<<" "<<time<<endl;
                res+=ps[index].value;
                index++;
            } else {
                break;

            }
        }
        printf("%d\n",res);
    }

    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */
发表于 2018-04-30 21:06:44 回复(1)
求助帖!急!
用python写的代码,运行了几个小例子都没有错,逐行运行也没有发现错误。但是提交会报答案错误,如下图:

源码附上,希望大佬们帮忙康康到底怎么回事:
import math

list1 = []
line = list(map(eval, input().split()))
for j in range(line[0]):
    li = list(map(eval, input().split()))
    list1 += li
list2 = sorted(list1, reverse=True)
Sum = 0
a = (list1.index(list2[0])) % line[1]
b = 0
time = 0
for i in range(len(list2)):
    if list2[i] == 0:
        break
    else:
        a_ = (list1.index(list2[i])) % line[1]
        b_ = math.ceil((list1.index(list2[i]) + 1) / line[1])
        if time + abs(a_ - a) + abs(b_ - b) + 1 + b_ <= line[2]:
            time += abs((a_ - a)) + abs((b_ - b)) + 1
            a, b = a_, b_
            Sum += list2[i]
            list1[list1.index(list2[i])] = 0
        else:
            break
print(Sum)


发表于 2020-05-07 19:29:14 回复(0)

详细解题思路:
https://fanxinglanyu.blog.csdn.net/article/details/104619003

2 解析

2.1 思路

  • 首先要理清题目信息:
    • 1 从第一行开始,最后一行回去,从路边到田间不花时间,每采一次花生花费一个时间单位;
    • 2 题目要求是在从多到少采花生的前提下,能最多采花生。
      步骤:
  • 1,记录每个花生的坐标以及数量(用结构体vector向量存储,方便使用STL的sort排序);
  • 2,按花生数量从大到小排序;
  • 3,枚举花生;
    • 如果本次采花生的花费(走路花费时间+采摘时间+返回时间【只做比较,不计入临时采花生的总花费】)小于或等于规定时间,则把本次采摘的数量计入采摘总量,继续循环;否则,结束循环。
    • 走路花费时间:(行列坐标差)【第一次采摘时的走路花费只计入列坐标的值】;
    • 采摘时间:【1个时间单位】;
    • 返回路边的时间(列坐标的值【要经过第一行到达路边】))小于或等于规定时间,则把本次采摘的数量计入采摘总量;
  • 4 输出最后采摘的总数量。

    2.2 样例解释

    设(x,y):(行,列)。
  • 1 从(0,2)【路边】出发到(4,2)【15处】;
    • 花费(走路:4 + 采摘 :1 + 返回:4)= 9 < 21,累计花费cost = 5,计入总量ans = 15;
  • 2 从(4,2)【15处】出发到(2, 5)【13处】;
    • 花费(走路:5 + 采摘 :1 + 返回:2)= 8 + 5 < 21,累计花费cost = 5 + 6 = 11,计入总量ans = 28;
  • 3 从(2, 5)【13处】出发到(5,4)【9处】;
    • 花费(走路:4 + 采摘 :1 + 返回:5)= 9 + 11 < 21,累计花费cost = 11 + 5 = 16,计入总量ans = 37;
  • 4 从(5 , 4)【13处】出发到(3,7)【9处】;
    • 花费(走路:5 + 采摘 :1 + 返回:3)= 9 + 16 > 21, 超过规定时间,不计入总量;
  • 5 输出答案:37

    3 参考代码

/*
 * 详解:
 */
#include <cstdio>
(802)#include <vector>
#include <algorithm>
(831)#include <cmath>

using std::vector;
using std::sort;

struct Peanut{
    int x;//列
    int y;//行
    int cnt;//个数
    Peanut(int _x, int _y, int _cnt):x(_x),y(_y),cnt(_cnt){}//构造函数
};

vector<Peanut> p;

bool cmp(Peanut a, Peanut b){
    return  a.cnt > b.cnt;
}


int main(int argc, char const *argv[]){
    int m, n, k;
    while(scanf("%d%d%d", &m, &n, &k) != EOF){
        p.clear();//清空上次存储的花生信息
        int tempCnt;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &tempCnt);
                if(tempCnt > 0){
                    p.push_back(Peanut(i, j, tempCnt));
                }
            }
        }
        sort(p.begin(), p.end(), cmp);//按采摘总数从大到小排序

        int cost = 0;
        int ans = 0;
        for (int i = 0; i < p.size(); ++i) {
            if(i == 0){
                cost += p[i].x + 1;//每次采花生所用时间(走路+采花生)
            }else{
                cost += abs(p[i].x - p[i-1].x) + abs(p[i].y - p[i-1].y) + 1;
            }


            if(cost + p[i].x > k){//如果本次采花生+回到路上的时间大于规定时间,
                break;// 本次采摘的花生数量不计入采摘总数
            }else{//在规定时间范围内,计入采摘总数
                ans += p[i].cnt;
            }
        }
        printf("%d\n", ans);

    }
    return 0;
}
发表于 2020-03-02 21:00:40 回复(0)
用例:
1
对应输出应该为:
0
你的输出为:
1

用例:
1
对应输出应该为:
1
你的输出为:
0



太好玩了
发表于 2019-10-23 22:40:49 回复(1)

我在codeblocks上运行的是正确结果呀,为什么说我输出是一个这么大的数,求解答


代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

struct node
{
    int value;
    int row;
    int col;
};

node a[410];
int arr[100][100];
int m, n, k;
int cnt;
int sum = 0;
int sumnum = 0;


bool cmp(node a, node b)
{
    if(a.value > b.value)
        return true;
    else
        return false;
}

int main()
{
    while(scanf("%d %d %d", &m, &n, &k) != EOF)
    {
        //cin >> m >> n >> k;

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> arr[i][j];
                if(arr[i][j] != 0)
                {
                    a[cnt].value = arr[i][j];
                    a[cnt].row = i;
                    a[cnt].col = j;
                    cnt++;
                }
            }
        }

        sort(a, a+cnt, cmp);
        /*
            for(int i = 0; i < cnt ;i++)
            {
                cout << a[i].value << " " << a[i].row << " " << a[i].col << endl;
            }
        */
        if(cnt == 0)
        {
            cout << 0;
            break;
        }

        sum = 0;
        sumnum = 0;
        for(int i = 0; i < cnt; i++)
        {
            if(i == 0)
            {
                sum += a[i].row;
            }
            else
            {
                sum = sum + abs(a[i-1].col - a[i].col) + abs(a[i-1].row - a[i].row);
            }


            if(sum + a[i].row < k)
            {
                sum += 1;
                sumnum += a[i].value;
            }
            else
            {
                cout << sumnum;
                break;
            }

        }
    }

    return 0;
}


发表于 2018-06-19 19:03:33 回复(0)
说一下这道题里面几个容易出问题的地方
1.仔细看题目,算法得和题目一样(从大到小排列每个非0位置的坐标,然后一个一个判断过去)
2.有的时候int不行就用long
3.注意考虑时间过多的情况,当程序对最后一个位置判断结束之后要跳出判断的循环
4.当程序判断到数量为0的位置的时候注意要让程序跳出循环,提高效率
发表于 2018-02-02 16:32:14 回复(1)
//这么简单的题目搞了几个小时,用纯C分分钟
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node
{
    int x;
    int y;
    int num;
}Peanut;
int cmp(const void *a, const void *b);
int main() 
{
    Peanut P[500];
    int M, N, K;
    int i, j, k;
    int value;
    while(~scanf("%d %d %d", &M, &N, &K))
    {
        k=0;         for(i=0;i<M;i++)         {             for(j=0;j<N;j++)             {                 scanf("%d", &value);                 if(value!=0)                 {                     P[k].num=value;                     P[k].x=i;                     P[k].y=j;                     k++;                 }             }         }         int lenP = k;         int s0, s1;         qsort(P, lenP, sizeof(Peanut), cmp);         Peanut O = {-1, P[0].y, 0};         for(i=0;i<lenP;i++)         {             s0 = abs(P[i].x-O.x)+abs(P[i].y-O.y) +1;              s1 = P[i].x+1;             if(s0+s1<=K) {                 O.num += P[i].num;                 O.x = P[i].x;                 O.y = P[i].y;                 K -= s0;             }             else             {                 break;             }         }         printf("%d\n", O.num);     }
    return 0;
}
int cmp(const void *a, const void *b)
{
    Peanut *A = (Peanut*)a;
    Peanut *B = (Peanut*)b;
    return B->num - A->num;
}

发表于 2017-11-26 11:50:01 回复(2)
import java.util.Scanner;

public class Main {
	
	 //采用了排序单链表的方式
	 //经常会出错时因为没有循环接收多组用例
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		//这个循环很重要
		while(scan.hasNext()) {
			int row = scan.nextInt();
			int column = scan.nextInt();
			int time = scan.nextInt();
			int temp = 0;
			SortedSinglyList list = new SortedSinglyList();
			for(int i = 0; i < row; i++) {
				for(int j = 0; j < column; j++) {
					temp = scan.nextInt();
					if(temp != 0) {
						list.insert(new Node(new Location(i,j,temp), null));
					}
				}
			}
			int sum = 0;
	
			Node p = list.getMax();
			if(p != null && time - p.data.row * 2 - 3 >= 0) {
				//首次进入时计算剩余时间是特殊情况
				sum += p.data.num;
				time = time - p.data.row - 2;
				//通常情况下计算剩余时间
				while(true) {
					Node now = p;
					p = list.getMax();
					//判断当前位置出去的剩余时间是否足够
					if(time < now.data.row + 1){
						sum -= now.data.num;
						break;
					}
					if(p != null){
						sum += p.data.num;
						//计算剩余时间
						time = time - Math.abs(now.data.row - p.data.row) - Math.abs(now.data.column - p.data.column) - 1;
					}
					else {
						break;
					}
				}
			}	
			System.out.println(sum);
		}

	}
}

class Location {

	 //保存非零的地址和数据

	int row,column,num;
	
	Location(int row, int column, int num) {
		this.row = row;
		this.column = column;
		this.num = num;
	}
	//按萝卜多少从大到小排序
	public int compareTo(Location a) {
		if(a.num < this.num) {
			return 1;
		}
		return 0;
	}

}

class Node {

	 //结点类

	public Location data;
	public Node next;
	
	public Node(){
		data = null;
		next = null;
	}
	
	public Node(Location data, Node next) {
		this.data = data;
		this.next = next;
	}	
}

class SortedSinglyList {
	
	public Node head;
	
	public SortedSinglyList() {
		head = new Node();
	}
	
	public void insert(Node temp) {
		Node front = head, p = front.next;
		if(p == null) {
			head.next = temp;
		}
		else {
			while(p != null && p.data.compareTo(temp.data) > 0) {
				front = p;
				p = p.next;
			}
			front.next = temp;
			temp.next = p;
		}
	}
	
	public Node getMax() {
		if(head.next != null) {
			Node p = head.next;
			head.next = p.next;
			return p;
		}
		else {
			return null;
		}
	}
}

编辑于 2017-04-18 22:00:37 回复(1)
C++
这道题目没想出来,总感觉哪里堵着。
然后扫了一眼讨论区的观点,发现有同学说自己题目都读错了,我怀疑自己也是审题有问题。于是我又把题目读了一遍,发现自己真的也读错了。自己只关注着输入和输出了,想当然地自以为题意就是在规定时间内获得最多的花生,而题目要求是从多到少采花生,出入很大。不过我感觉题目的要求更简单些。
所以我重新把题目理了一遍:
0
0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
13是(2,5)
7是(3,7)
13到7的话可以用行列索引凑出来,可以发现13到7要经过3步,而3=(3-1)+(7-5),所以从一个有花生的植株到另一颗有花生的植株可以用行列计算出来
首先,我想的是肯定要知道那些有花生的植株的行列,从而得到
13 7 15 9
2 3 4 5
5 7 2 5
再对上面表格注释一下
13 7 15 9
2 3 4 5
5 7 2 4
因为首先要采最多的花生,所以对花生表格排序一下,排序有好几种方法,能想到的最弱智的方法就是逐个比较了,先用这个方法,等有了时间限制再考虑替换排序算法,毕竟这道题目主要目的不是排序。
好了,排序之后的表格如下
15 13 9 7
4 2 5 3
2 5 4
7
理想情况下的采摘顺序是15 13 9 7,如果时间超过了,则省掉7,如果还是超,再省掉9,如果还是超,就再省掉13,如果还是超,就再省掉15,如果还是超,那就返回了,因为已经没花生可以采了。当然了本题输入限时21,全采的话用时4+5+4+5+3+4=25,所以必须省掉7,此时要用时4+5+4+5+3=21,正好。
解释:
其中全采的时候,4(路边调到15处)+5(15->13)+4(13->9)+5(9->7)+3(7回到路边)+4=25
所以算法基本流程是清楚的,所以题目要求感觉简化了很多,因为如果题目要求求解规定时间下的最多采摘花生数,感觉有点麻烦了。
下面就是如何用C++实现,我对如何处理输入感觉疑惑,参考了下问答区的Java,感觉应该是用流输入处理。至于如何用C++处理流输入,可以谷歌一下,谷歌的方法是,输入关键词 “C++ get 2d array input”可以发现真的好多人都在问这个问题,所以我们的需求真的很普通,选择前几个搜索结果基本就能解答了。



发表于 2017-11-02 10:42:25 回复(5)
while(    scanf("%d %d %d", &m, &n, &k) != EOF )
{
    //处理过程
}
记得要这样来处理输入,不然会出现测试用例 1 通不过的情况
发表于 2018-03-17 11:53:52 回复(2)
测试用例:
1

对应输出应该为:

1

你的输出为:

0
怎么回事。。。
发表于 2018-02-24 13:46:19 回复(7)
测试用例:
1

对应输出应该为:
1
这是什么情况???
发表于 2019-03-21 23:24:22 回复(0)
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int x, y;//花生所在行与列
    int count;//花生个数
    bool flag = true;//当前是否被采摘
};

int main() {
    //输入 m n k m行 n列 k个单位时间 sum最多采摘数量
    int m, n, k,sum = 0;
    int length = 0;//存储数组的长度
    // c_x,c_y当前位置, c_k当前剩余时间,temp临时变量 ,count循环次数
    // index 当前局部最优位置
    int c_x = 0, c_y = 0,temp = 0,c_k = 0, count = 0, index = 0;
    Node nodes[999] = {};//存储输入的花生数据
    int Y_sum = 0;//最终最多采集
    scanf_s("%d %d %d", &m, &n, &k);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; ++j) {
            scanf_s("%d", &nodes[length].count);
            nodes[length].x = i + 1;
            nodes[length].y = j + 1;
            length++;
        }
    }    
    //遍历从路边进入某列花生树
    for (int i = 0; i < n;++i) {
        //更新当前位置以及当前位置花生数,循环次数,重置是否被采集
        count = 0;
        sum = 0;
        c_x = 1;
        c_y = i; 
        temp = nodes[i].count;
        c_k = k - 1;
        for (int i = 0; i < length;++i) {
            nodes[i].flag = true;
        }
        //最多循环m*n次
        while (count < m*n) {
            //寻找本次循环最优花生数量,并记录局部最优位置
            for (int i = 0; i < length; ++i) {
                if (temp < nodes[i].count && nodes[i].flag) {
                    temp = nodes[i].count;
                        index = i;
                }    
            }
            //局部最优位置,如果符合采摘要求
            if (nodes[index].count != 0 && c_k >= 1+ 1 + nodes[index].y +
                abs(c_x - nodes[index].x) + abs(c_y - nodes[index].y)) {
                sum += nodes[index].count;
                c_k = c_k - abs(c_x - nodes[index].x) -
                    abs(c_y - nodes[index].y);
                c_x = nodes[index].x;
                c_y = nodes[index].y;
                nodes[index].flag = false;
                temp = 0;
                index = 0;
            }
            count++;
        }
        //从不同的地方开始(第一行某一个花生树开始)有不同的sum
        if (Y_sum < sum) {
            Y_sum = sum;
        }
    }
    printf("%d",Y_sum);
    return 0;
}

大佬们这哪错了,我只能通过一个例子,思路就是暴力解
编辑于 2024-02-09 19:47:34 回复(0)
这道题的题意很好理解,就是代码的实现需要很多细节,把细节全部走一遍流程,没问题才是对的
发表于 2022-10-09 21:24:21 回复(0)
输入:1
????小朋友你是否有很多问号
发表于 2020-04-04 21:38:54 回复(0)
为什么测试用例是 1 1 0  ,而没有输入数组
发表于 2020-03-13 17:46:41 回复(0)
这个题真的很坑,也是我审题不清,我想的花生地是单独一块地,可以从四条边上进入,我写完之后调试一直比要求输出的大,调了几次我就怀疑是我看错题了,重新看题才发现原来只能从第-1行开始进入,删掉了几个条件判断之后就完事了。所以说一定要好好审题啊。。

#include <stdio.h>
#include <stdlib.h>
 
typedef struct hs
{
    int num;//花生数量
    int hs_x;
    int hs_y;//所在位置
}HS;
 
int cmp(const void* a, const void* b)
{
    HS *h1 = (HS*) a;
    HS *h2 = (HS*) b;
    return (h2 -> num - h1 -> num);
}//从大到小排列
 
HS hs[400];
 
int main()
{
    int m, n, t;
    while(~scanf("%d %d %d", &m, &n, &t))
    {
        //int field[20][20] = {0};//田里花生的矩阵
        int i, j;
        int ammount = m*n;//田地面积
        int count = 0;
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
            {
                hs[count].hs_x = i;
                hs[count].hs_y = j;
                scanf("%d", &(hs[count].num));
                count++;
            }
        if(ammount < 400)    hs[ammount].num = 0;//最后一个元素置为0
        qsort(hs, ammount, sizeof(hs[0]), cmp);
        int x, y;
        x = -1;            y = hs[0].hs_y;
        int sum = 0;
        i = 0;
        while(x+1 < t && hs[i].num)//x,y>=t时必须返回,若有花生的地方全部采摘完毕也必须返回
        {
            if(hs[i].hs_x == x && hs[i].hs_y == y)
            {
                sum += hs[i].num;
                i++;
                t--;
                continue;
            }
             
            if(hs[i].hs_x > x)//目标花生在多多右边
            {
                x++;
                t--;
                continue;
            }
            else if(hs[i].hs_x < x)//目标花生在多多左边
            {
                x--;
                t--;
                continue;
            }
             
            if(hs[i].hs_y > y)//目标花生在多多上边
            {
                y++;
                t--;
                continue;
            }
            else if(hs[i].hs_y < y)//目标花生在多多下边
            {
                y--;
                t--;
                continue;
            }
        }
        printf("%d\n", sum);
    }
}


编辑于 2020-03-01 13:30:07 回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct node {
	int val;
	int x;
	int y;
	node(int p1, int p2, int p3) {
		x = p1;
		y = p2;
		val = p3;
	}
};
bool cmpFun(const node& n1, const node& n2) {
	return n1.val > n2.val;
}
int main() {
	int c = 0;
	int r = 0;
	int time = 0;
	int temp = 0;
	while (cin >> c >> r >> time) {
		vector<node> nlist;
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < r; j++) {
				cin >> temp;
				if (temp > 0) {
					nlist.push_back(node(i, j, temp));//只保留有花生的庄稼位置和花生数
				}
			}
		}
		sort(nlist.begin(), nlist.end(), cmpFun);//按照花生数从大到小排序
		int count = 0;    //记录已摘花生数
		int  px = -1, py = nlist[0].y;    //记录目前所在位置
		for (int i = 0; i < nlist.size(); i++) {
			int nx = nlist[i].x, ny = nlist[i].y;
			int consume = abs(nx - px) + abs(ny - py) + 1;//所消耗的时间
			if (time - consume < nx + 1) {//判断如果去摘下一个花生,能否安全回到路边
				break;
			}
			else {
				time -= consume;
				count += nlist[i].val;
				px = nx;
				py = ny;
			}
		}
		cout << count << endl;
	}
}

编辑于 2020-02-23 17:11:23 回复(0)