首页分享 CSP历年复赛题

CSP历年复赛题

来源：花匠小妙招时间：2024-12-14 03:48

原题链接：https://www.luogu.com.cn/problem/P1086

题意解读：按照花生数从多到少去采摘花生，每次是否采下一株需要看剩余时间是否足够返回路边，够则剩余时间减掉采摘下一株所需时间，不够则直接返回路边。

解题思路：

样例模拟，如图所示，时间限制为21

按照花生数量将每棵植株排序，

第一步：是否采第一棵？

当前剩余时间21，完成第一棵采集所需时间为1+3+1 = 5, 采集完第一棵返回路边的时间为3+1 = 4，21 - 5- 4 > 0，因此可以采第一棵，采第一棵后时间剩下21 - 5 = 16

第二步：是否采第二棵？

当前剩余时间16，完成第二棵采集所需时间为5+1 = 6，采集完第二棵返回路边的时间为1+1 = 2,16 - 6 - 2 > 0，因此可以采第二棵，采第二棵后时间剩下16 - 6 = 10

第三步：是否采第三棵？

当前剩余时间10，完成第三棵采集所需时间为4+1 = 5，采集完第三棵返回路边的时间为4+1 = 5,10-5-5=0，因此可以采第三棵，采第三棵后时间剩下0

第四步：是否采第四课？

当前剩余时间0，显然无法再采。

模拟以上过程，实现代码即可，注意每个动作的时间累计：

1、从路边到第一行，1单位时间

2、花生田中没移动一格，1单位时间

3、采摘花生，1单位时间

4、从第一行跳到路边，1单位时间

另外，要计算两个点(x1,y1),(x2,y2)之间的距离，采用abs(y2-y1)+abs(x2-x1)

100分代码：

#include <bits/stdc++.h> using namespace std; int n, m, k; struct node { int x, y, w; }; node a[405]; int cnt; int ans; bool cmp(node a, node b) { return a.w > b.w; } int main() { cin >> n >> m >> k; int w; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> w; if(w > 0) { a[++cnt].w = w; a[cnt].x = i; a[cnt].y = j; } } } sort(a + 1, a + cnt + 1, cmp); int lastx = 0, lasty = a[1].y; //上一个花生的位置，初始放在和第一个花生同列的路上 for(int i = 1; i <= cnt; i++) { int t1 = abs(a[i].y - lasty) + abs(a[i].x - lastx) + 1; //走到下一个花生的位置并采摘所需时间 int t2 = a[i].x; //从下一个花生位置返回路边所需时间 if(k < t1 + t2) break; //剩下的时间不够采摘下一个花生且返回 ans += a[i].w; //够采则采摘 k -= t1; //剩余时间减去t1 lastx = a[i].x, lasty = a[i].y; //更新上一个花生位置 } cout << ans; return 0; }

网址: CSP历年复赛题 https://www.huajiangbk.com/newsview1085611.html

所属分类：花卉