花生采摘(算法分析与设计swust oj 348)
·



分析与方案:
花生采摘:首先定义一个花生植株节点points,包含其所处的行号x,列号y,以及花生数num,定义一个以points为数据的花生园数组。从索引值为1开始依次输入m*n个数据,然后将数组[1]~[m*n]根据每一个花生节点的花生数,从大到小进行排序,索引值为0为路边,它的x值为0,y值为第一个结点的y值,m*n+1是最后回到路边的位置,它的x值为0,y值为[m*n]节点的y值。初始花生数为numbers,首先计算走到第一个采集点采栽后剩余时间tmp,然后循环,如果小于当前节点的x值,那么无法采摘到当前节点的花生,numbers=0,退出循环。如果tmp小于到下一个采集点所需走的时间加上下一个节点回到路边所需的时间,那么回不到路边,加上当前节点的花生数,退出循环。如果tmp>=到下一个采集点所需走的时间加上下一个节点回到路边所需的时间,下一采集点可以回到路边,加上当前节点的花生数,tmp减去采摘时间1和到下一个采集点所需走的时间。
流程图:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct points{
int num;
int x;
int y;
};
bool comp(points a,points b){
return (a.num>b.num);
}
int walk(points a,points b){
//相隔的距离
return abs(a.x-b.x)+abs(a.y-b.y);
}
int main(){
int steps;
int numbers;//花生数目
points p[2502];//花生园
int m,n;
cin>>m>>n>>steps;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin>>p[i*n+j+1].num;
p[i*n+j+1].x=i+1;
p[i*n+j+1].y=j+1;
}
}
sort(p+1,p+m*n+1,comp);
p[0].x=0;p[0].y=p[1].y;
p[m*n+1].x=0;p[m*n+1].y=p[m*n].y;
numbers=0;
int tem=steps-walk(p[0],p[1])-1;//走到第一个采集点采栽后剩余步数
for(int i=1;i<=m*n;i++){
if(p[i].num==0)break;
if(tem<p[i].x){//回不到路边
numbers=0;
break;
}else if(tem<p[i+1].x+1+walk(p[i],p[i+1])){
//下一采集点回不到路边
numbers+=p[i].num;
break;
}else{
//下一采集点可以回到路边
numbers+=p[i].num;
tem-=(walk(p[i],p[i+1])+1);
}
}
cout<<numbers<<endl;
}
更多推荐




所有评论(0)