信息学奥赛一本通 1927：【04NOIP普及组】花生采摘 |
您所在的位置：网站首页 › noip普及组获奖有什么用 › 信息学奥赛一本通 1927：【04NOIP普及组】花生采摘 |
|
【题目链接】
ybt 1927：【04NOIP普及组】花生采摘 OpenJudge NOI 1.13 38:花生采摘 洛谷 P1086 [NOIP2004 普及组] 花生采摘 【题目考点】 1. 模拟 2. 贪心 【解题思路】该题一定要仔细看题，题目中有： 鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 所以不是我们决定一条能够采花生的路线，而是这个鲁宾逊已经指定了采花生的顺序，狗只能按照他给的贪心的思路不断采有花生最多的植株。我们只需要判断什么时候要让狗停止采摘回到路边。 设变量t表示已经用过的时间。在采摘下一个植株前，先计算一下t加上走到下一个植株、采摘、再回去所用的时间是否超出给定的时间。 如果超出，那么现在就回去如果没超出，再采摘下一株在这一过程中，统计采摘到的花生数。 从(x1, y1)到(x2, y2)的时间，为这两点间的曼哈顿距离，为 ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x1-x2|+|y1-y2| ∣x1−x2∣+∣y1−y2∣ 【题解代码】 解法1：使用数组填充，冒泡排序 #include using namespace std; #define N 25 struct Node { int x, y, n;//(x,y)有n个花生 }; int main() { Node a[405]; int an = 0, m, n, k, t = 0, ans = 0;//t：用掉的时间 ans:采到的花生 cin >> m >> n >> k; for(int i = 1; i cout t += abs(a[i].x-a[i-1].x) + abs(a[i].y-a[i-1].y) + 1;//到a[i]位置，采一株 ans += a[i].n; } } cout } Node(int a, int b, int c):x(a), y(b), n(c){} bool operator return abs(a.x-b.x) + abs(a.y-b.y); } int main() { vector vec; int a, m, n, k, t = 0, ans = 0;//t：用掉的时间 ans:采到的花生 cin >> m >> n >> k; for(int i = 1; i cout t += dis(vec[i], vec[i-1]) + 1;//到vec[i]位置，采一株 ans += vec[i].n; } } cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |