匿名网友
问题描述: 小V今年有n门课，每门都课都有考试。为了拿到奖学金，小V必须让自己的平均年成绩至少为avg，每门课的最终成绩由平时成绩和考试成绩组成，满分为r，现在他知道每门课的平时成绩为ai，如果想要让自己这门课的成绩多拿一分的话，小V必须花bi小时复习，不花时间意味着这门课的考试成绩只能拿0分，平时成绩加考试成绩超过r这么课最终成绩也只能按r计算。为了拿到奖学金，请问小V至少需要花多少时间复习功课？ 输入：
输入两行数据，第一行是两个整数：路灯数目n(1<=n<=1000)，街道长度(1<=l<=pow(10, 9))。第二行有n个整数ai(0<=ai<=l)，表示路灯坐标，多个路灯可以在同一个地方，也可以安放在终止点位置。
样例输入：
5 5 4
5 2
4 7
3 1
3 2
2 5
结果:
4
Hint:
花两个小时复习第三门考试拿两分，两个小时复习第四门考试拿一分，这样总平均成绩为(5+4+5+4+2)/4 = 4
解题思路：对第i门课程，如果要增加1分，需要花费bi个小时的时间，为了耗费的时间最小，我们肯定应该选那些增加1分所用时间短的课程复习。
代码步骤：先以bi(也就是以样例中的时间列)为排序基准，对由ai和bi组成的矩阵(二维数组)由小到大排序，然后逐步由花费时间最小的课程开始(也就是排序后的第一行)逐步增加1分，判断总分数是否到了avg*n，到了就停止，否则继续加1分。
下面是自己写的参考代码，没考虑输入边界情况，写得比较渣，思路比较好理解。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(int argc, const char * argv[]) {
int n, r, avg;
cin >> n >> r >> avg;
vector<int> A(n);
vector<int> B(n);
for(int i = 0; i < n; i++){
int tmpAi, tmpBi;
cin >> tmpAi >> tmpBi;
A[i] = tmpAi;
B[i] = tmpBi;
}
vector<size_t> indexes(n);
size_t nn(0);
generate(begin(indexes), end(indexes), [&]{return nn++;});
sort(begin(indexes), end(indexes), [&](int i1, int i2){return B[i1] < B[i2];});
vector<int> sortedA(n);
vector<int> sortedB(n);
for(int i = 0; i < n; i++){
sortedB[i] = B[indexes[i]];
sortedA[i] = A[indexes[i]];
}
int sum = accumulate(sortedA.begin(), sortedA.end(), 0);
int time = 0;
int i = 0;
while((sum < avg*n) && (i < n)){
int addScores = 0;
while((sortedA[i] + addScores) < 5 && sum < avg*n){
sum = sum + 1;
time = time + sortedB[i];
++addScores;
}
++i;
}
cout << time << endl;
return 0;
}
问题描述: V先生有一天工作得很晚，回家的时候要穿过一条长度为l的笔直街道，这条街道上有n个路灯。假设这条街起点为0，终点为l，第i个路灯的坐标为ai。路灯发光能力以正数d来衡量，其中d表示路灯能够照亮的街道上的点与路灯的最远距离，所有路灯发光能力相同。为了让V先生看清回家的路，路灯必须照亮整天街道，又为了节省电力希望找到最小的d是多少？
输入：
输入两行数据，第一行是两个整数：路灯数目n(1<=n<=1000)，街道长度(1<=l<=pow(10, 9))。第二行有n个整数ai(0<=ai<=l)，表示路灯坐标，多个路灯可以在同一个地方，也可以安放在终止点位置。
样例输入：
7 15
15 5 3 7 9 14 0
结果：
2.5
解题思路：找出相邻坐标差值中最大的，然后除以2便是最小的d。
代码步骤：先进行输入处理，将其保存在looc中，再对其进行由小到大的排序，然后计算找出相邻坐标中最大的差值。 下面是自己写的参考代码，没考虑输入边界情况，写得比较渣，思路比较好理解。
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
int numBulb, distance;
cin >> numBulb >> distance;
vector<int> looc(numBulb);
for(int i = 0; i < numBulb; i++){
int tmp;
cin >> tmp;
looc[i] = tmp;
}
sort(looc.begin(), looc.end(), less<int>());
int maxDis = 0;
for(int i = 0; i < numBulb; i++){
int tmp = looc[i+1]-looc[i];
if(tmp > maxDis)
maxDis = tmp;
}
cout << maxDis/2.0 << endl;
return 0;
}
