1382 I’M大胃王
描述
【背景】
2008.11.16
3721大班在Mr Lv 的组织下，到六食堂举办了一次集体包饺子活动：）
这次活动很成功，大家都很高兴，所谓“有缘千里，相聚北航”。
下来后，某人根据这次活动出了一套练习题……
------------------------------------------------
o(∩_∩)o…哈哈，这个活动好玩，每个小班派个代表，比赛谁在30秒（还是1分钟？）内吃的饺子数目最多，可以喝水！
最后的胜利者是Mr Wang吧，当“采访”的时候他一语道破了成功秘诀：
“其实当比赛开始前我做了一些工作；
有很多盘饺子放在我面前吧，我会先选择一些盘吃，毕竟时间不多，换盘子要时间；
我选择的规则是：
首先先把我面前的平面划分成N*M个方格，某些方格中有盘子，并且知道盘子中饺子的数量；对于没有盘子的位置，记为0；
然后从最多到最少饺子数量来选择好盘数，我估计我可以干掉R盘，所以只选择R盘；
但是有一点，两盘之间的距离如果大于了P，我就不会选择下一盘，跳过去，直到按照排序下来某个盘的距离小于等于P；
详细解释下：比如我吃第i盘的时候位置是（3，3），按照排序下一盘位置是（1，1），但是P是2，我就不会选择了，这里P定义为|x1-x2|+|y1-y2|，直接跳到下面一盘，就是按照饺子个数从大到小排序好的序列，假设这个盘子位置是（3，2）那么就可以选择作为第I+1盘饺子了；
当然如果按照这个规矩选择下来不足R盘也算了……
恩~谢谢党和人民，谢谢Mr. Lv 给我这个证明自己算法正确的机会……
”
头晕了吧……现在作为评委，请你按照这个规矩计算出他吃的饺子数目；
- 输入
-
输入数据第一行包含一个整数T，表示有T组测试数据；
对于每组测试数据：
第一行包含4个整数N,M,R,P。各个数据含义如题；
接下来是个N*M的矩阵，各个元素是一个非负整数；
保证N和M均小于等于100，R小于N*M，P大于0；
这里为了没有歧义，保证每个盘子中饺子数目都不相等；
输出 -
请按照题目描述规则输出大胃王吃掉的饺子个数；
样例输入 -
1
-
5 5 3 3
-
0 0 0 0 2
-
0 5 0 0 0
-
0 0 1 0 0
-
3 0 0 4 0
-
0 0 0 0 0
样例输出 -
9
-
（解释：5+3+1）
模拟题
#include
#include
#includeusing namespace std;struct node{int x;int y;int data;
};node a[10001];bool cmp(node a, node b)
{return (a.data > b.data);
}int main()
{int t;scanf("%d", &t);while(t --){int n, m, r, p;scanf("%d%d%d%d", &n, &m, &p, &r);int i, j, k;k = 0;for(i = 0; i != n; i ++)for(j = 0; j != m; j ++){scanf("%d", &a[k].data);if(a[k].data != 0){a[k].x = i;a[k].y = j;++ k;}}sort(a, a + k, cmp);j = 0;int sum = 0;sum += a[j].data;node temp;temp = a[j];++ j;int amount = 1;while(amount < p){if(abs(a[j].x - temp.x)+ abs(a[j].y - temp.y) <= r){sum += a[j].data;temp = a[j];amount ++;}j ++;if(j > k)break;}printf("%d\n", sum);}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！