[NOIP普及组 2004] 花生采摘 {快速排序}

#题目
题目描述

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！――熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图 11 ）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里，只有位于 (2, 5), (3, 7), (4, 2), (5, 4)(2,5),(3,7),(4,2),(5,4) 的植株下长有花生，个数分别为 13, 7, 15, 913,7,15,9 。沿着图示的路线，多多在 2121 个单位时间内，最多可以采到 3737 个花生。

输入输出格式

输入格式：
第一行包括三个整数，$ M, N 和 和 和K$ ，用空格隔开；表示花生田的大小为$ M times N(1 le M, N le 20)M×N(1≤M,N≤20) $，多多采花生的限定时间为 K ( 0 ≤ K ≤ 1000 ) K ( 0 ≤ K ≤ 1000 ) K(0 le K le 1000)K(0≤K≤1000) K(0≤K≤1000)K(0≤K≤1000) 个单位时间。接下来的 MM 行，每行包括 NN 个非负整数，也用空格隔开；第$ i + 1i+1 行 的 第 行的第 行的第 j 个 整 数 个整数 个整数 P_{ij}(0 le P_{ij} le 500)P ij​ (0≤P ij​ ≤500) 表 示 花 生 田 里 植 株 表示花生田里植株 表示花生田里植株 (i, j)(i,j) $下花生的数目， 00 表示该植株下没有花生。

输出格式：
一个整数，即在限定时间内，多多最多可以采到花生的个数。

#结题思路

先将花生从小到大排序，每次尝试跳到下一棵植株，如果此时已经来不及跳回路边，就立即停止（这次的花生并没有采摘到），从上一次的植株直接跳回路边，否则就采摘这次的花生。

#代码

#include<bits/stdc++.h> using namespace std; struct node{int x,y,w; }a[402]; int m,n,k,t,ans; bool cmp(node x,node y) { return x.w>y.w; } int main() {scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {a[++t]={i,j,0};scanf("%d",&a[t].w); }sort(a+1,a+n*m+1,cmp);a[0].x=0;a[0].y=a[1].y;for (int i=1;i<=n*m;i++){k-=abs(a[i-1].x-a[i].x)+abs(a[i-1].y-a[i].y)+1;if (k<a[i].x) break;ans+=a[i].w;}printf("%d",ans); }

相关知识

NOIP初赛知识
新浪赛盟2004年度联欢会总结
中国人过敏性休克诱因首度排序 食物排首位
内蒙古24人采摘沙葱韭菜花被查处：非法采摘野生植物
冒泡排序，选择排序，二分法查找，顺序查找
冒泡排序
排序宠物拼图(Sort Pet Puzzle)下载
公园里的禁止采摘提示牌高清图片下载
媒体采风走进城阳 体验田园采摘、亲子研学等活动
python求组合数cnm公式

网址: [NOIP普及组 2004] 花生采摘 {快速排序} https://www.mcbbbk.com/newsview554202.html