|
三、编程题（每题 25 分，共 50 分）
1. 小杨买饮料
问题描述
⼩杨来到了⼀家商店，打算购买⼀些饮料。这家商店总共出售N 种饮料，编号从 0⾄N-1，其中编号为 i 的饮料售价 ci 元，容量 li 毫升。 ⼩杨的需求有如下⼏点：
1.⼩杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买1 瓶； 2.⼩杨很渴，所以他想要购买总容量不低于 L 的饮料； 3.⼩杨勤俭节约，所以在 1 和 2 的前提下，他希望使用尽可能少的费用。⽅便起见，你只需要输出最少花费的费用即可。特别地，如果不能满⾜⼩杨的要求，则输出 no solution. 输入描述
第⼀⾏两个整数 N, L。
接下来 N ⾏，依次描述第 i= 0,1,...,N-1 种饮料：每⾏两个整数 ci , li 。 输出描述
输出⼀⾏⼀个整数，表⽰最少需要花费多少钱，才能满足⼩杨的要求。特别地，如果不能满足要求，则输出 no solution 。
特别提醒
在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任何提⽰信息。
样例输入 1 5 100
100 2000
2 50
4 40
5 30
3 20
样例输出 1
9
样例解释 1
小杨可以购买 1，2，4 号饮料，总计获得 50+40+20=110 毫升饮料，花费2+4+3=9元。
如果只考虑前两项需求，小杨也可以购买 1，3，4 号饮料，它们的容量总和为50+30+20=100 毫升，恰好可以满足需求。但遗憾的是，这个方案需要花费2+5+3=10 元。
样例输入 2
5 141
100 2000
2 50
4 40
5 30
3 20
样例输出 2
100
样例解释 2
1，2，3，4 号饮料总计 140 毫升，如每种饮料至多购买1 瓶，则恰好无法满足需求，因此只能花费 100 元购买 0 号饮料。
样例输入 3
4 141
2 50
4 40
5 30
3 20
样例输出 3
no solution
数据规模
对于 40% 的测试点，保证 N ≤ 20；1 ≤ L ≤100；li ≤ 100。
对于 70% 的测试点，保证 li ≤ 100。
对于所有测试点，保证 1≤ N ≤ 500；1 ≤ L ≤ 2000；1 ≤ ci, li ≤ 106。 【题目大意】
有 n 种饮料，每种饮料只能选 1 瓶，相当于有 n 瓶饮料，每种饮料只有两种状态：选或者不选，即 0 和 1。选择饮料的升数最高是 L 升，表示有上限。希望尽可能的少花钱，就是求满足条件的最小值。符合 01 背包的问题。 【考纲知识点】
基本运算、输入输出语句、循环、动态规划的知识。
【解题思路】
按题目要求定义好需要的变量，并实现输入；
输入 n 行，每行 2 个整数，分别表示饮料的零售价和升数； 初始化边界，买 0 升饮料的费用肯定是 0，其他初始化为最大值； 每种饮料都要参与判断，选还是不选，更新 L~0 需要的费用； 最终求出 L 升饮料需要的费用。
【参考程序】 #include <iostream>
using namespace std;
const int INF=1000000000;
int cost[2001];
int main(){
int N=0, L=0;
cin >>N >> L;
cost[0]=0;
for(int i=1;i<=L; i++)
cost[i]= INF;
for(int i=0;i<N; i++){
int c=0, l=0;
cin>>c >>l;
for(int j=L;j>=0;j--)
cost[j]=min(cost[j],cost[max(j-l,0)]+ c);
}
if(cost[L]== INF)
cout<< "no solution" << endl;
else
cout<< cost[L]<< endl;
return 0;
}
2.小杨的握手问题
问题描述
小杨的班级里共有 N 名同学，学号从 0 至 N-1。
某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班 N 名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学号小于自己的同学握手。
现在，小杨想知道，整个班级总共会进行多少次握手。 提示
可以考虑使用归并排序进行降序排序，并在此过程中求解。 输入描述
输入包含 2 行。第一行一个整数 N，表示同学的个数；第二行N 个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0～N-1 之间，表示该同学的学号。
保证每位同学会且只会进入教室一次。
输出描述
输出一行一个整数，表示全班握手的总次数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任 何提示信息。
样例输入 1 4
2 1 3 0
样例输出 1
2
样例解释 1
2 号同学进入教室，此时教室里没有其他同学。
1 号同学进入教室，此时教室里有 2 号同学。1 号同学的学号小于2 号同学，因此他们之间不需要握手。
3 号同学进入教室，此时教室里有 1，2 号同学。3 号同学的学号比他们都大，因此 3 号同学需要分别和另外两位同学握手。
0 号同学进入教室，此时教室里有 1，2，3 号同学。0 号同学的学号比他们都小，因此 0 号同学不需要与其他同学握手。
综上所述全班一共握手 0+0+2+0=2 次。
样例输入 2
6
0 1 2 3 4 5
样例输出 2
15
样例解释 2
全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号是当前教室里最大的，所以他需要和教室里的每位其他同学进行握手。数据规模
对于 30% 的测试点，保证 N ≤ 100。
对于所有测试点，保证 2 ≤ N ≤ 3 × 105。
【题目大意】
有 n 个学生，假设第 i 个学生进入教师，找出前 1~i-1 个学生，哪些人的学号比自己小，小的需要握手，贡献值加 1。
【考纲知识点】
基本运算、输入输出语句、循环、归并排序的知识。
【解题思路】
按题目要求定义好需要的变量，并实现输入；
输入 n 个整数，每个数字分别和前面的数字进行比较，如果大于，贡献值加1。可以用双重循环模拟，找到答案；
因为数据范围是 300000，双重循环会超时。
归并排序可以求逆序对，逆序对是指：ia[j]；本题相当于“顺序对”,i>j,a[i]>a[j]，同样可以用归并排序求得，时间复杂度是O(Nlogn)。写归并排序，在排序的过程中，统计数量，求和可得结果。
【参考程序】 #include <iostream>
using namespace std;
int num[300000];
int tmp[300000];
long long merge(int l,int r){
if(l+1==r)
return 0;
int m=(l+r)/2;
long long res=merge(l,m)+ merge(m,r);
for(int i=l,j=m,k=l;k<r;k++){
if(j==r || (i<m && num[i] > num[j])){
tmp[k]=num[i];
i++;
} else {
tmp[k]= num[j];
j++;
res += m-i;
}
}
for(int k=l;k<r; k++)
num[k]=tmp[k];
return res;
}
int main(){
int n = 0;
cin>>n;
for(int i = 0;i<n;i++){
cin>>num[i];
}
cout<<merge(0,n)<<endl;
return 0;
}
(责任编辑：lizq) |