采矿时间到时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述你已经获得了木头通过工作台制作了木镐获得了圆石和石镐现在你已经可以采掘铁矿石了。这一天你挖了一条长度为n nn宽度为1 11的矿道你最多只能在这条矿道向左/右正方向拓宽2 22格并且你只能垂直于矿道挖掘。##*#############**## #########*########## .................... #####*######**###### #*##################如上图所示′ . ′ .′.′表示矿道′ # ′ \#′#′表示的是圆石′ ∗ ′ *′∗′表示的是矿石。本题固定第三行为矿道第一/二行 为你的左侧第四/五行 为你的右侧。因为你只能站在矿道上至多向左/右正方向拓宽2 22格所以本题只给出5 ∗ n 5∗n5∗n的俯视图。每拓宽一格需要花费1 11点体力。现在您有h hh点体力问你最多能得到多少矿石以下是合法的两种挖法###.## ###..# ###.## ###..#...-......-...### ### ### ### ### ### ### ###以下是不合法的两种挖法###..# ###...###.## ### #.#...-......-...### ### ### ### ### ### ### ###输入描述第一行 两个正整数n nn和h hhn nn为 矿道的长度h hh为体力大小。接下来五行 每行一个长度为n nn的只含有′ # ′ \#′#′′ ∗ ′ *′∗′和′ . ′ .′.′的字符串′ # ′ \#′#′表示圆石′ ∗ ′ *′∗′表示矿石′ . ′ .′.′表示矿道。五行中的第三行一定全为′ . ′ .′.′。1 ≤ n ≤ 1000 1≤n≤10001≤n≤10000 ≤ h ≤ 4000 0≤h≤40000≤h≤4000输出描述一个整数表示你最多能得到的矿石数量。示例1输入20 7 ##*#######**######## #########*########## .................... #####*######**###### ####################输出5说明##*#######.*######## #########..######### .................... #####.######..###### ####################如上刚好采掘6 66格花费6 66点体力得到5 55个矿石。备注解题思路本题核心是贪心策略解决限定体力下最多采集矿石的问题。矿道固定为5行结构第三行为安全区域向左1、2行、向右4、5行垂直挖掘遵循优先挖体力消耗最小的矿石原则。根据规则2行、4行的矿石挖掘成本为1体力1行、5行的矿石必须先挖相邻格子总成本为2体力。遍历整个矿场统计所有矿石的挖掘成本将成本从小到大排序依次消耗体力采集矿石直到体力不足为止最终采集的数量即为最大矿石数。算法时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)完美适配题目数据范围。总结核心逻辑贪心优先选择挖掘成本最低的矿石用有限体力获取最大数量。关键操作计算每块矿石的挖掘成本、成本排序、贪心选取矿石。效率保障排序线性遍历逻辑简洁无冗余计算轻松处理题目约束。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,h;cinnh;vectorvectorcharg(n1,vectorchar(6));for(ll i1;i5;i)for(ll j1;jn;j)cing[j][i];vectorllc;for(ll i1;in;i){if(g[i][2]*)c.push_back(1);if(g[i][4]*)c.push_back(1);if(g[i][1]*){if(g[i][2]*)c.push_back(1);elsec.push_back(2);}if(g[i][5]*){if(g[i][4]*)c.push_back(1);elsec.push_back(2);}}sort(c.begin(),c.end());ll ans0;for(ll i0;i(ll)c.size();i){h-c[i];if(h0)ans;elsebreak;}coutansendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T1;while(T--)solve();return0;}