前言

本文记录4月27日晚7点一场软件开发岗笔试的题目，思路以及代码实现。

一、题目简介

题目：
购买水果最便宜的方案
具体描述：
m个水果超市在1~n个小时的不同时间段提供不同价格的打折水果，如果某餐厅在每个小时都要采购一种水果给餐厅使用的话，请选出n个小时内，采购水果的最便宜的花费总和（假设m个超时打折时间段可以覆盖n小时）
输入输出：
输入：
5
3
1 2 30
1 5 20
3 5 10
第一行表示5个小时，第二行表示有3个水果超市，第三行到第五行中的每一行分别表示每个超市开始提供水果的时间，结束提供水果的时间以及提供水果的价格。
输出：
70
第1，2小时选第二家超市采购，第3，4，5小时选第三家超时采购价格最便宜，共70元。

二、思路

这应该是到目前为止最简单的一道笔试题，相比与前几次笔试的第一题，比如查找舆情热词和硬件资源的最佳分配，本题同样不需要什么算法技巧，而且题意简单易懂，且没有什么复杂的判别条件和特殊情况，可以直接秒杀。我们直接枚举每个时间点，对于每个时间点选择在此时间点上供应水果的水果超市，再从这些水果超市中选择最便宜的价格，最后将每个时间点上的最低价格加起来就行了。

三、C++代码实现

#include<iostream>
#include<vector>using namespace std;
int n, m;struct Shop
{int begin, end, price;
};int main()
{cin >> n >> m;vector<Shop> shop(m);for (int i = 0; i < m; i++) cin >> shop[i].begin >> shop[i].end >> shop[i].price;int res;for (int i = 1; i <= n; i++){int min_price = INT32_MAX;for (int j = 0; j < m; j++){if (shop[j].begin <= i && shop[j].end >= i) min_price = min(min_price, shop[j].price);}res += min_price;}cout << res << endl;return 0;
}