正版素材网站,wordpress显示标签图片,沈阳网站建设 南塔,厦门十大装修公司排名榜A - 汽车加油问题
Description
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法#xff0c;指出应在哪些加油站停靠加油#xff0c;使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置#xff0c;计算最少加油次数。
I…A - 汽车加油问题
Description
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法指出应在哪些加油站停靠加油使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置计算最少加油次数。
Input
输入数据的第一行有2 个正整数n和kn≤5000k≤1000表示汽车加满油后可行驶n公里且旅途中有k个加油站。接下来的1 行中有k1 个整数表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地汽车已加满油。第k1 个加油站表示目的地。
Output
将计算出的最少加油次数输出。如果无法到达目的地则输出“No Solution!”。
Samples
Sample #1
Input
Output
7 7
1 2 3 4 5 1 6 6
4
#includebits/stdc.h
using namespace std;
const int N 1005;
int a[N];
//0 1 1 1 1 1 1 1 0
// 1 5 4 5 4 3 3 3
int main()
{int n, k;int cnt 0;bool flag 0;cin n k;for(int i 0; i k; i){cin a[i];if(a[i] n){flag 1;}}int d n;if(flag) cout No Solution! \n;else{for(int i 0; i k; i){if(d a[i]){d - a[i];}else{d n;cnt;d - a[i];}}cout cnt \n;}return 0;
}
B - 多元Huffman编码问题
Description
在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆合并的费用为新的一堆的石子数。试设计一个算法计算出将n堆石子合并成一堆的最大总费用和最小总费用。 对于给定n堆石子,计算合并成一堆的最大总费用和最小总费用。
Input
输入数据的第1 行有2 个正整数n和kn≤100000k≤10000表示有n堆石子每次至少选2 堆最多选k堆石子合并。第2 行有n个数每个数均不超过 100分别表示每堆石子的个数。
Output
将计算出的最大总费用和最小总费用输出两个整数之间用空格分开。
Samples
Sample #1
Input
Output
7 3
45 13 12 16 9 5 22
593 199
Hint
请注意数据范围是否可能爆 int。
#includebits/stdc.h
using namespace std;
typedef long long LL;
int main()
{int n, k;cin n k;priority_queueint, vectorint, greaterint q1;priority_queueint q2;for(int i 0; i n; i){int x;cin x;q1.push(x);q2.push(x);}LL sum1 0, sum2 0;while(q1.size() % (k-1) ! 1){q1.push(0);}while(q1.size() 1){LL sum 0;for(int i 0; i k; i){sum q1.top();q1.pop();}sum1 sum;q1.push(sum);}while(q2.size() 1){LL sum 0;int a q2.top();q2.pop();int b q2.top();q2.pop();sum (a b);sum2 sum;q2.push(sum);}cout sum2 sum1 \n;return 0;
}
C - 装船问题
Description
王小二毕业后从事船运规划工作吉祥号货轮的最大载重量为M吨有10种货物可以装船。第i种货物有wi吨总价值是pi。王小二的任务是从10种货物中挑选若干吨上船在满足货物总重量小于等于M的前提下运走的货物的价重比最大。
Input
输入数据的第一行有一个正整数M(0 M 10000)表示所有货物最大载重量。在接下来的10行中每行有若干个数中间用空格分开第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍0 pi , wi 1000)
Output
输出一个整数表示可以得到的最大价值。
Samples
Sample #1
Input
Output
100
10 10
20 10
30 10
40 10
50 10
60 10
70 10
80 10
90 10
100 10
550
Hint
价重比计算其价值与重量之比
#includebits/stdc.h
using namespace std;
const int N 12;
int p[N], w[N], c[N];
int main()
{int m;cin m;for(int i 0; i 10; i){cin p[i] w[i];c[i] p[i] / w[i];}for(int i 0; i 9; i){for(int j i; j 10; j){if(c[i] c[j]){int t p[i];p[i] p[j];p[j] t;t w[i];w[i] w[j];w[j] t;t c[i];c[i] c[j];c[j] t;}}}int sum 0;for(int i 0; i 10; i){if(m w[i]){m - w[i];sum p[i];}else{sum c[i] * m;break;}}cout sum \n;return 0;
}
D - 活动选择
Description
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放但活动中心同时只能供一个社团活动使用并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划即活动的开始时刻和截止时刻。请设计一个算法来找到一个最佳的分配序列以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。 比如有5个活动开始与截止时刻分别为 最佳安排序列为1,4,5。
Input
第一行输入活动数目0100 以后输入行分别输入序号为1到的活动使用中心的开始时刻与截止时刻a,b为整数且0a,b24a,b输入以空格分隔。
Output
输出最佳安排序列所包含的各个活动按照活动被安排的次序两个活动之间用逗号分隔如果有多个活动安排序列符合要求输出字典序最小的序列。
Samples
Sample #1
Input
Output
6
8 10
9 16
11 16
14 15
10 14
7 11
1,5,4
#includebits/stdc.h
using namespace std;
const int N 110;
struct activity
{int num;int start;int endd;int flag;
}act[N], t;
int main()
{int n;cin n;for(int i 0; i n; i){act[i].num i 1;cin act[i].start act[i].endd;act[i].flag 0;}for(int i 0; i n - 1; i){for(int j 0; j n - 1 - i; j){if(act[j].endd act[j1].endd){t act[j];act[j] act[j1];act[j1] t;}}}int s 0;for(int i 0; i n; i){if(act[i].start s){act[i].flag 1;s act[i].endd;}}printf(%d, act[0].num);for(int i 1; i n; i){if(act[i].flag 1){printf(,%d, act[i].num);}}printf(\n);return 0;
}
E - 最优合并问题
Description
给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序使所需的总比较次数最少。 为了进行比较还需要确定合并这个序列的最差合并顺序使所需的总比较次数最多。 对于给定的k个待合并序列计算最多比较次数和最少比较次数合并方案。
Input
输入数据的第一行有1 个正整数kk≤1000表示有k个待合并序列。接下来的1 行中有k个正整数表示k个待合并序列的长度。
Output
输出两个整数中间用空格隔开表示计算出的最多比较次数和最少比较次数。
Samples
Sample #1
Input
Output
4
5 12 11 2
78 52
#includebits/stdc.h
using namespace std;
const int N 1e3 10;
int a[N], b[N];
bool cmp(int a, int b){return a b;
}
int main()
{int k;cin k;for(int i 0; i k; i){cin a[i];b[i] a[i];}sort(a, a k);// 默认降序sort(b, b k, cmp);// 升序int maxn 0, minn 0;for(int i 0; i k - 1; i){a[i1] a[i] a[i1];minn a[i1];sort(ai1, ak);b[i1] b[i]b[i1];maxn b[i1];sort(bi1, bk, cmp);}cout maxn - k 1 minn - k 1 \n;return 0;
}
