徒步1
# 问题描述
小明想从A徒步到B，总路程需要M天，路程中为了确保安全，小明每天需要消耗1份食物。
在起点及路程当中，零星分布着N个补给站，可以补充食物，不同补给站的食物价格可能不同。
请问小明若要安全完成徒步，最少需要花费多少钱呢？
## 输入格式
第一行为两个正整数`M`、`N`，代表总路程`M`天，补给站个数`N`
接下来`N`行，每行有两个非负整数`A`、`B`代表一个补给站，表示第`A`天经过该补给站，每份食物的价格为`B`元。
`A`是从0开始严格递增的，即起点一定有补给站，补给站是按位置顺序给出的，且同一个位置最多有一个补给站。
## 输出格式
输出一个整数，表示最少花费的金额
## 输入样例
```
5 4
0 2
1 3
2 1
3 2
```
## 输出样例
7
思路
好久没有做过这种贪心题目了，这道题如果按照题意去模拟计算那可真是麻烦坏了，如果从头开始按照题意去计算是很难得到正确的答案的
本题要求最小的花费，每个补给站的价格不一样，所以我们直接寻找价格最低的补给站去购买尽可能多的食物，这个时候就不能从头开始走了，我们要从终点向起点走，因为对于价格最低的商店我们买了它的食物只能在他的后面食用，就像上面那个样例，我们在2号补给站购买足以到终点的食物，然后找价格第二低的补给站购买足够的食物，直到走到起点
先对存放补给站信息的二维数组按照食物价格从低到高排序，然后从价格最低的那个补给站购买足以到达终点的食物，同时将终点坐标设置为该补给站的坐标，这样从前往后遍历的同时判断补给站的坐标是否小于终点坐标，小于的话就执行上面的操作，大于的话直接跳过即可，遍历完一遍数组就可以得到最终答案了。
public static int solution(int m, int n, int[][] p) {
Arrays.sort(p,new Comparator<int[] >() {
public int compare(int[] a,int[] b){
return a[1]-b[1];
}
});
int res=0;
for(int[] x:p){
if(x[0]>=m){
continue;
}
res+=(m-x[0])*x[1];
m=x[0];
}
return res;
}
对于这类题目，如果按照正常的思维去模拟的话是很难写出正解的，可是只要察觉到了它的贪心之处我们就可以轻松的解决，往往贪心题目中都要求求出最小次数之类的答案，同时需要利用排序辅助计算。
相关知识
年轻人产生“徒步依赖” 90后户外爱好者一年建了19个徒步群，成员破万人
南美安第斯山脉徒步穿越,哥伦比亚篇回忆录
园林园艺行业第一届戈壁徒步穿越挑战赛启动仪式在北京举行
花海漫步在杭州：春天最美的徒步路线
2024福州闽清山地户外节徒步越野比赛时间和地点
光福徒步大会打造人文户外品牌
2024东莞松山湖科学城徒步活动报名入口+方式
直击！平胜蝴蝶兰文化节开锣！徒步、文化街超热闹！
2024福州闽清山地户外节徒步越野比赛参赛要求
2024福州闽清杜鹃花海徒步越野比赛组委会联系方式
网址: 徒步1 https://m.huajiangbk.com/newsview860790.html
| 上一篇: 昆明寻甸花石头山爬山旅游攻略（自 |
下一篇: 收藏！济南“定制”春日游上线！这 |
