算法分析与设计(三)

http://192.168.173.163/JudgeOnline/contest.php?cid=1253

密码:123654

算法实验3

评分系统

题目描述

英语俱乐部举办了一个叫做“英文金曲大赛”的节目。这个节目有好多人参加,这不,成绩出来了,渊子当是很勇敢,自告奋勇接下了算出大家的总得分的任务。当时有7个评委,每个评委都要给选手打分,现在要求去掉一个最高分和去掉一个最低分,再算出平均分。结果精确到小数点后两位。

输入

测试数据包括多个实例。每组数据包括7个实数,代表评委们对该选手的评分。紧接着是选手的名字,名字的长度不超过30个字符。输入直到文件结束。

输出

输出每位选手名字和最终得分,结果保留两位有效数字。

样例输入

1
2
10 10 10 10 10 10 9 xiaoyuanwang
0 0 0 0 0 0 0 beast

样例输出

1
2
xiaoyuanwang 10.00
beast 0.00

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int main() {
string name;
double score[7];
while (cin >> score[0]) {
for (int i = 1; i < 7; i++) {
cin >> score[i];
}
cin >> name;
sort(score, score+7);
double sum = 0;
for (int i = 1; i < 6; i++) {
sum += score[i];
}
cout << name << " " << fixed << setprecision(2) << sum / 5 << endl;
}
return 0;
}

节食的限制

题目描述

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在限制范围内最多可以吃多少公斤的乾草。

样例输入

1
2
3
4
5
56 4
15
19
20
21

样例输出

1
56

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include<algorithm>
using namespace std;
int s[51];
int dp[45001] = { 0 };

int main() {
int H, n;
cin >> H >> n;
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int j = H; j >= s[i]; j--) {
dp[j] = max(dp[j], dp[j - s[i]] + s[i]);
}
}
cout << dp[H] << endl;
return 0;
}

汽车费用

题目描述

一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。没有一辆车子行驶超过10公里,一个顾客打算行驶n公里(1<=n<100),它可以通过无限次的换车来完成旅程。最后要求费用最少。

输入

第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义,即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示,旅客的总路程数。

输出

仅一个整数表示最少费用。

样例输入

1
2
12 21 31 40 49 58 69 79 90 101
15

样例输出

1
147

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int cost[11];
int dp[102];

int main() {
for (int i = 1; i <= 10; i++) {
cin >> cost[i];
}
memset(dp, INF, sizeof(dp));
dp[0] = 0;
int n;
cin >> n;
for (int i = 1; i <= 10; i++) {
for (int j = 1; j <= n; j++) {
if (j >= i)
dp[j] = min(dp[j], dp[j - i] + cost[i]);
}
}
cout << dp[n] << endl;
return 0;
}

法师傅的工人

题目描述

三个法师康的工人每天早上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的非负整数数据,表示其中一个工人的生产开始时间与结束时间。

输出

输出为一行,用空格分隔开两个我们所求的数。

样例输入

1
2
3
4
3
200 1000
700 1100
1500 2100

样例输出

1
900 400

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f;
typedef long long ll;
struct work {
ll begin;
ll end;
}a[5001];

bool cmp(work a, work b) {
return a.begin < b.begin;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].begin >> a[i].end;
}
sort(a, a + n, cmp);
ll l = a[0].begin, r = a[0].end;
ll s = r - l, t = 0;
for (int i = 1; i < n; i++) {
if (r >= a[i].begin) {
r = max(r, a[i].end);
s = max(s, r - l);
}
else {
l = a[i].begin;
t = max(t, l - r);
r = a[i].end;
}
}
cout << s << " " << t << endl;
return 0;
}

配对元素

题目描述

给出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。

样例输入

1
2
3
4
2 5 6 3
1 4 6 7

样例输出

1
14

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[10001];
int b[10001];

bool cmp(int a, int b) {
return a > b;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
sort(a, a + n);
sort(b, b + n, cmp);
long long sum = 0;
for (int i = 0; i < n; i++) {
sum += abs(a[i] - b[i]);
}
cout << sum << endl;
return 0;
}
-------------end ♥-------------