【算法课OJ】实验三
云无心以出岫，鸟倦飞而知还。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1113
密码：123654
问题 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
题意
输入7个数字（double）和人名。
输出人名和去掉最高分和最低分后的平均分。
思路
Water。开一个数组存7个分数，输入完sort()函数一下，最低分在a[0]，最高分在a[6]，那我们直接写个for循环求a[1]+a[2]+...+a[5]（当然你也可以不用循环直接相加）然后除5输出即可。
代码
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int main()
{
double a[7];
char nam[35];
while(~scanf("%lf",&a[0]))
{
for(int i = 1; i < 7; i++)
{
scanf("%lf",&a[i]);
}
scanf("%s",nam);
sort(a,a+7);
double sum = 0;
for(int i = 1; i < 6; i++)
{
sum += a[i];
}
sum /= 5;
printf("%s %.2lf\n",nam,sum);
}
return 0;
}
问题 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
题意
在n个物品中任意选取，总重要尽量大且不超过h。
思路
典型的0-1背包题，不同的是重量和价值是一样的。
递归函数：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int dp[55][45002];
int main()
{
int h,n,w[55];
scanf("%d %d",&h,&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&w[i]);
}
for(int i = 0; i <= h; i++)
dp[0][i] = 0;
for(int i = 1; i <= n; i++)
dp[i][0] = 0;
for(int i = 1; i <= n; i++)
{
int jMax = min(h,w[i]);
for(int j = 1; j < jMax; j++)
dp[i][j] = dp[i-1][j];
for(int j = w[i]; j <= h; j++)
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
}
printf("%d\n",dp[n][h]);
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
题意
给一张价格表，对应1-10km分别多少钱，可通过无限次的换车来完成旅程。输入一个距离，求最少费用。
思路
dp，有最优子结构性质。
完全背包问题。把距离看成背包，先求出1km的最小价格，再求出2km的最小价格……直到求出n km的最小价值。
代码
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[105];
int main()
{
int n;
for(int i = 1; i <= 10; i++)
{
scanf("%d",&dp[i]);
}
scanf("%d",&n);
for(int i = 11; i <= n; i++)
dp[i] = inf;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < i; j++)
{
dp[i] = min(dp[i],dp[j]+dp[i-j]);
}
}
printf("%d\n",dp[n]);
return 0;
}
问题 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
题意
有n个线段区间。给出左界l和右界r，求最长的至少被一条线段覆盖的连续区间长度和最长的没被线段覆盖的区间长度。
思路
ans1指最长的至少被一条线段覆盖的连续区间长度。
ans2值最长的没被线段覆盖的区间长度。
输入后，先按开始时间从小到大排序。
可以把多个连续的区间（相交或相切）看成一个区间，如何实现呢？
a[j].e = max(a[i].e,a[j].e);
a[j]为上一个连续区间。这时候如果连续区间>ans1那么更新下ans1。
这样遇到不连续的且断裂的长度>ans2就更新下ans2，再把当前区间赋给j（成为上一个区间）。
代码
#include<iostream>
#include<algorithm>
#include<stdio.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;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d %d",&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;
}
}
printf("%d %d\n",ans1,ans2);
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
题意
思路
Water，Greedy。
先对两个数组排下序，然后用个变量ans存储答案。
为了让差值和最大，那我们就取a中最小和b中最大，a中第二小和b中第二大……
代码
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn = 1e4 + 5;
int main()
{
int n,a[maxn],b[maxn],ans = 0;
scanf("%d",&n);
for(int i = 0; i < n ; i++)
{
scanf("%d",&a[i]);
}
for(int i = 0; i < n ; i++)
{
scanf("%d",&b[i]);
}
sort(a,a+n);
sort(b,b+n);
for(int i = 0; i < n; i++)
{
ans += abs(a[i]-b[n-1-i]);
}
printf("%d\n",ans);
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/19/algorithm-experiment-3/