算法实验三。
问题 A: 评分系统
题目描述
英语俱乐部举办了一个叫做“英文金曲大赛”的节目。这个节目有好多人参加，这不，成绩出来了，渊子当是很勇敢，自告奋勇接下了算出大家的总得分的任务。当时有7个评委，每个评委都要给选手打分，现在要求去掉一个最高分和去掉一个最低分，再算出平均分。结果精确到小数点后两位。
输入
测试数据包括多个实例。每组数据包括7个实数，代表评委们对该选手的评分。紧接着是选手的名字，名字的长度不超过30个字符。输入直到文件结束。
输出
输出每位选手名字和最终得分，结果保留两位有效数字。
样例输入
10 10 10 10 10 10 9 xiaoyuanwang
0 0 0 0 0 0 0 beast
样例输出
xiaoyuanwang 10.00
beast 0.00
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
double a[7],sum=0;
while(cin>>a[0])
{
sum=a[0];
for(int i=1;i<7;i++)
{
cin>>a[i];
sum+=a[i];
}
sort(a,a+7);
string s;
cin>>s;
cout<<s<<" ";
sum=sum-a[0]-a[6];
sum=sum/5.0;
cout<<setprecision(2)<<std::fixed<<sum<<endl;
}
}
问题 B: 节食的限制
题目描述
Bessie像她的诸多姊妹一样，因為从Farmer John的草地吃了太多美味的草而长出了太多的赘肉。所以FJ将她置於一个及其严格的节食计划之中。她每天不能吃多过H(5<=H<=45000)公斤的乾草。Bessie只能吃一整綑乾草；当她开始吃一綑乾草的之后就再也停不下来了。她有一个完整的N(1<=n<=50)綑可以给她当作晚餐的乾草的清单。她自然想要尽量吃到更多的乾草。很自然地，每綑乾草只能被吃一次（即使在列表中相同的重量可能出现2次，但是这表示的是两綑乾草，其中每綑乾草最多只能被吃掉一次）。 给定一个列表表示每綑乾草的重量Si(1<=Si<=H),求Bessie不超过节食的限制的前提下可以吃掉多少乾草（注意一旦她开始吃一綑乾草就会把那一綑乾草全部吃完）。
输入
第一行：两个由空格隔开的整数：H和N， 第2到N+1行：第i+1行是一个单独的整数，表示第i綑乾草的重量Si。
输出
一个单独的整数表示Bessie在限制范围内最多可以吃多少公斤的乾草。
样例输入
56 4
15
19
20
21
样例输出
56
提示
代码
#include<bits/stdc++.h>
using namespace std;
int dp[45001];
int main()
{
int h,z,a[501];
cin>>h>>z;
for(int i=1;i<=z;i++)
cin>>a[i];
for(int i=1;i<=z;i++)
for(int j=h;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
cout<<dp[h]<<endl;
return 0;
}
问题 C: 汽车费用
题目描述
一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。没有一辆车子行驶超过10公里，一个顾客打算行驶n公里(1<=n<100)，它可以通过无限次的换车来完成旅程。最后要求费用最少。
输入
第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示，旅客的总路程数。
输出
仅一个整数表示最少费用。
样例输入
12 21 31 40 49 58 69 79 90 101
15
样例输出
147
提示
代码
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int a[11],v[105];
int main()
{
for(int i=1;i<=10;i++)
{
cin>>a[i];
}
int n;
cin>>n;
for(int i=1;i<105;i++)
{
v[i]=inf;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=10;j++)
{
if(i>=j)
{
v[i]=min(v[i],v[i-j]+a[j]);
}
}
}
cout<<v[n]<<endl;
}
问题 D: 法师康的工人
题目描述
三个法师康的工人每天早上6点到工厂开始到三条产品生产线上组装桔子手机。第一个工人在200时刻开始（从6点开始计时，以秒作为单位）在生产线上开始生产，一直到1000时刻。第二个工人，在700时刻开始，在1100时刻结束。第三个工人从1500时刻工作到2100时刻。期间最长至少有一个工人在生产线上工作的连续时间为900秒（从200时刻到1100时刻），而最长的无人生产的连续时间（从生产开始到生产结束）为400时刻（1100时刻到1500时刻）。
你的任务是用一个程序衡量N个工人在N条产品线上的工作时间列表（1≤N≤5000，以秒为单位）。
·最长的至少有一个工人在工作的时间段
·最长的无人工作的时间段（从有人工作开始计）
输入
输入第1行为一个整数N，第2-N+1行每行包括两个均小于1000000的非负整数数据，表示其中一个工人的生产开始时间与结束时间。
输出
输出为一行，用空格分隔开两个我们所求的数。
样例输入
3
200 1000
700 1100
1500 2100
样例输出
900 400
提示
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
struct node
{
int b,e;
bool operator < (const node& c) const
{
return b < c.b;
}
}a[maxn];
int main()
{
int n,ans1,ans2;
cin>>n;
for(int i = 0; i < n; i++)
{
cin>>a[i].b>>a[i].e;
}
sort(a,a+n);
ans1 = a[0].e - a[0].b;
ans2 = 0;
int j = 0;
for(int i = 1; i < n; i++)
{
if(a[i].b <= a[j].e) //如果交叉或相切
{
a[j].e = max(a[i].e,a[j].e);
ans1 = max(ans1,a[j].e-a[j].b);
}
else
{
ans2 = max(ans2,a[i].b-a[j].e);
j = i;
}
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}
问题 E: 配对元素
题目描述
给出2个序列A={a[1]，a[2]，…，a[n]}，B={b[1]，b[2]，…，b[n]}，从A、B中各选出n个元素进行一一配对（可以不按照原来在序列中的顺序），并使得所有配对元素差的绝对值之和最大。
输入
输入的第1行为1个整数n 第2行包含n个整数，题目中的A序列。 第3行包含n个整数，题目中的B序列。
输出
一个数，最大配对
3与6配对，2与7配对，5与4配对，6与1配对，绝对值之差和为14 对于10%的数据，有n≤20； 对于30%的数据，有n≤100； 对于50%的数据，有n≤1000； 对于100%的数据，有n≤10000；a[i]，b[i]≤1000。
样例输入
4
2 5 6 3
1 4 6 7
样例输出
14
提示
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
sort(a,a+n);
sort(b,b+n);
int sum=0;
for(int i=0;i<n;i++)
{
sum=sum+abs(a[i]-b[n-1-i]);
}
cout<<sum<<endl;
}
