湖南大学829考研资料829-C语言编程题

二、编程题（除8,10,12，其它题需要掌握）1.问题描述近来，跳一跳这款小游戏风靡全国，受到不少玩家的喜爱。简化后的跳一跳规则如下：玩家每次从当前方块跳到下一个方块，如果没有跳到下一个方块上则游戏结束。如果跳到了方块上，但没有跳到方块的中心则获得1分；跳到方块中心时，若上一次的得分为1分或这是本局游戏的第一次跳跃则此次得分为2分，否则此次得分比上一次得分多两分（即连续跳到方块中心时，总得分将+2，+4，+6，+8.）。现在给出一个人跳一跳的全过程，请你求出他本局游戏的得分（按照题目描述的规则）。输入格式输入包含多个数字，用空格分隔，每个数字都是1，2，0之一，1表示此次跳跃跳到了方块上但是没有跳到中心，2表示此次跳跃跳到了方块上并且跳到了方块中心，0表示此次跳跃没有跳到方块上（此时游戏结束）。输出格式输出一个整数，为本局游戏的得分（在本题的规则下）。样例输入1 1 2 2 2 1 1 2 2 0样例输出22数据规模和约定对于所有评测用例，输入的数字不超过30个，保证0正好出现一次且为最后一个数字。问题分析： 一个简单的序列处理问题。 输入到文件结束或最后一个数为0。程序说明： 变量plus用于存储加分。初值为0，连续得2分则每次增加2分，如果得1分（没有跳到中心）则加分变为0分。/* CCF201803-1 跳一跳 */#include using namespace std;int main() int a, sum = 0, plus = 0; while(scanf(%d, &a) != EOF & a) sum += a; if(a = 1) plus = 0; else if(a = 2) sum += plus; plus += 2; printf(%dn, sum); return 0;2.问题描述数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒。当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小。当两个小球撞到一起的时候，两个小球会分别向与自己原来移动的方向相反的方向，以原来的速度大小继续移动。现在，告诉你线段的长度L，小球数量n，以及n个小球的初始位置，请你计算t秒之后，各个小球的位置。提示因为所有小球的初始位置都为偶数，而且线段的长度为偶数，可以证明，不会有三个小球同时相撞，小球到达线段端点以及小球之间的碰撞时刻均为整数。同时也可以证明两个小球发生碰撞的位置一定是整数（但不一定是偶数）。输入格式输入的第一行包含三个整数n, L, t，用空格分隔，分别表示小球的个数、线段长度和你需要计算t秒之后小球的位置。第二行包含n个整数a1, a2, , an，用空格分隔，表示初始时刻n个小球的位置。输出格式输出一行包含n个整数，用空格分隔，第i个整数代表初始时刻位于ai的小球，在t秒之后的位置。样例输入3 10 54 6 8样例输出7 9 9样例说明初始时，三个小球的位置分别为4, 6, 8。一秒后，三个小球的位置分别为5, 7, 9。两秒后，第三个小球碰到墙壁，速度反向，三个小球位置分别为6, 8, 10。三秒后，第二个小球与第三个小球在位置9发生碰撞，速度反向（注意碰撞位置不一定为偶数），三个小球位置分别为7, 9, 9。四秒后，第一个小球与第二个小球在位置8发生碰撞，速度反向，第三个小球碰到墙壁，速度反向，三个小球位置分别为8, 8, 10。五秒后，三个小球的位置分别为7, 9, 9。样例输入10 22 3014 12 16 6 10 2 8 20 18 4样例输出6 6 8 2 4 0 4 12 10 2数据规模和约定对于所有评测用例，1 n 100，1 t 100，2 L 1000，0 ai L。L为偶数。保证所有小球的初始位置互不相同且均为偶数。问题分析： 这是一个模拟题，按照时间序列进行模拟，模拟小球的运动过程。好在每个时间单位小球只移动一个位置，处理起来就要简单一些。模拟题关键在于采用什么样的数据表示，这里给出2种解法。 方法一（不排序，暴力）： 使用数组posi存储第i个球的初始位置；使用数组stepi存储第i个球现在的运动方向，stepi=1表示向右走，stepi=-1表示往左走，用加法运算就可以实现小球的移动。 模拟过程是按照时间序列，先计算小球的下一个位置，如果该位置为两端则改变运动方向。再根据小球的新位置看看有没有2个小球碰头，有的话分别改变运动方向。只是简单地判断2个小球是否碰头需要用暴力法算一下。 方法二（结构数组，排序）： 如果不想用暴力，则将有关参数放入一个结构数组中，给每一个小球编号，排序后再进行模拟，输出结果时再按照编号重新排序即可。程序说明：（略）题记： 没有好办法就暴力，没有好办法就模拟。这个题正好应验了这两句话。/* CCF201803-2 碰撞的小球 */法一：#include using namespace std;const int L = 1000;int posL + 1, stepL + 1;int main() int n, l, t; cin n l t; for(int i = 0; i posi; / 开始往右走，到达两端则回头 stepi = 1; if(posi = l | posi = 0) stepi = -stepi; for(int i = 0; i t; i+) / 走一步 for(int j = 0; j n; j+) posj += stepj; / 到达两端则回头 if(posj = l | posj = 0) stepj = -stepj; / 判断是否碰头，碰头则掉头（要避免重复比较） for(int j = 0; j n; j+) for(int k = j + 1; k n; k+) if(posk = posj) stepk = -stepk, stepj = -stepj; for(int i = 0; i n; i+) cout posi ; cout endl; return 0; /* CCF201803-2 碰撞的小球 */ #include #include using namespace std;const int N = 100;struct Node int id; / 小球编号 int pos; / 位置 int step; / 运动方向，1表示向右，-1表示向左 bN; bool cmp1(Node a, Node b) return a.pos b.pos;bool cmp2(Node a, Node b) return a.id n l t; for(int i = 0; i bi.pos; / 开始往右走，到达两端则回头 bi.step = 1; if(bi.pos = l | bi.pos = 0) bi.step = -bi.step; sort(b, b + n, cmp1); for(int i = 0; i t; i+) / 走一步 for(int j = 0; j n; j+) bj.pos += bj.step; / 到达两端则回头 if(bj.pos = l | bj.pos = 0) bj.step = -bj.step; / 判断是否碰头，碰头则掉头（排序后只需要比较相邻的） for(int j = 1; j n; j+) if(bj.pos = bj - 1.pos) bj.step = -bj.step, bj - 1.step = -bj - 1.step; sort(b, b + n, cmp2); for(int i = 0; i n; i+) cout bi.pos ; cout endl; return 0;3.卖菜问题描述在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。第一天，每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。给定第一天各个商店的菜价，请计算第二天每个商店的菜价。输入格式输入的第一行包含一个整数n，表示商店的数量。第二行包含n个整数，依次表示每个商店第一天的菜价。输出格式输出一行，包含n个正整数，依次表示每个商店第二天的菜价。样例输入84 1 3 1 6 5 17 9样例输出2 2 1 3 4 9 10 13数据规模和约定对于所有评测用例，2 n 1000，第一天每个商店的菜价为不超过10000的正整数。#include using namespace std;int a1001;int main()int n;cinn;for(int i=0;iai;for(int i=0;in;i+)if(i=0)cout(int)(a0+a1)/2 ;else if(i=(n-1)cout(int)(an-1+an-2)/2endl;elsecout(int)(ai-1+ai+ai+1)/3 ;return 0;4.买菜问题描述小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段a1,b1,a2,b2.an,bn在装车，对于小W来说有n个不相交的时间段c1,d1,c2,,dn在装车。其中，一个时间段s, t表示的是从时刻s到时刻t这段时间，时长为t-s。由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。输入格式输入的第一行包含一个正整数n，表示时间段的数量。接下来n行每行两个数ai，bi，描述小H的各个装车的时间段。接下来n行每行两个数ci，di，描述小W的各个装车的时间段。输出格式输出一行，一个正整数，表示两人可以聊多长时间。样例输入41 35 69 1314 152 45 710 1113 14样例输出3数据规模和约定对于所有的评测用例，1 n 2000, ai bi ai+1，ci di ci+1,对于所有的i(1 i n)有，1 ai, bi, ci, di 1000000。#include int h200003;int main() int n;/段数 int time = 0;/次数 int c, d;/录入小w scanf(%d, &n);/输入段数 /录入小h for (int i = 0; i n; +i) scanf(%d%d, &hi0, &hi1); /录入小W for (int j = 0; j n; j+) scanf(%d%d, &c, &d);/输入c ,d for (int i = 0; i = hi0 & c hi1) time += hi1 - c; /记录聊天数 c = hi1; else time += d - c; /图二 else if (hi0 c & hi0 d) if (d = hi1) time += d - hi0; d=hi0; else time += hi1 - hi0; printf(%d, time); return 0; 5.问题描述（最小差数）给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。输入格式输入第一行包含一个整数n。第二行包含n个正整数，相邻整数之间使用一个空格分隔。输出格式输出一个整数，表示答案。样例输入51 5 4 8 20样例输出1样例说明相差最小的两个数是5和4，它们之间的差值是1。样例输入59 3 6 1 3样例输出0样例说明有两个相同的数3，它们之间的差值是0.数据规模和约定对于所有评测用例，2 n 1000，每个给定的整数都是不超过10000的正整数。问题分析： 根据题意，这是一个求所有数差值最小的问题。 有两种方法可以解决，一是用暴力法；二是先对所有数据进行排序，然后求相邻数差值的最小值（变成求最值问题）。程序说明： 绝对值函数abs()要使用stdlib.h库中的函数。 求最小值的初值要设置成最大值，原题中指出数最大值为10000，所以初值取10000即可。/* CCF201712-1 最小差值 */ #include #include using namespace std;const int N = 1000;const int N2 = 10000;int aN; int main() int n; / 读入数据 cin n; for(int i=0; i ai; / 排序 sort(a, a + n); / 计算差值的最小值 int min = N2; for(int i=1; in; i+) int d = ai - ai - 1; if(d min) min = d; / 输出结果 cout min endl; return 0;6.问题描述有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，1号小朋友坐在n号小朋友的顺时针方向。游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。例如，当n=5, k=2时：1号小朋友报数1；2号小朋友报数2淘汰；3号小朋友报数3；4号小朋友报数4淘汰；5号小朋友报数5；1号小朋友报数6淘汰；3号小朋友报数7；5号小朋友报数8淘汰；3号小朋友获胜。给定n和k，请问最后获胜的小朋友编号为多少？输入格式输入一行，包括两个整数n和k，意义如题目所述。输出格式输出一行，包含一个整数，表示获胜的小朋友编号。样例输入5 2样例输出3样例输入7 3样例输出4数据规模和约定对于所有评测用例，1 n 1000，1 k 9。 这是一个模拟题，关键在于数据表示。 另外，使用模除可以实现循环，即下标的循环。这是程序中经常用的技术。程序说明： 方法一： 使用数组进行模拟，flag用于标记小朋友是否出局，flagi=false表示i+1号小朋友没有出局，flagi=true表示i+1号小朋友已经出局。 程序中的其他做法都是套路。/* CCF201712-2 游戏 */ #include#include#includeusing namespace std; int main() int n,k; queue q; / 读入数据与队列初始化 scanf(%d%d,&n,&k); for(int i=1; i=n; i+) q.push(i); / 模拟出局过程 int no=0, head; while(!q.empty() head = q.front(); q.pop(); no+; if(no % k = 0 | no % 10 = k) ; else q.push(head); printf(%dn, head); return 0;7.问题描述小明带着N元钱去买酱油。酱油10块钱一瓶，商家进行促销，每买3瓶送1瓶，或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。输入格式输入的第一行包含一个整数N，表示小明可用于买酱油的钱数。N是10的整数倍，N不超过300。输出格式输出一个整数，表示小明最多可以得到多少瓶酱油。样例输入40样例输出5样例说明把40元分成30元和10元，分别买3瓶和1瓶，其中3瓶送1瓶，共得到5瓶。样例输入80样例输出11样例说明把80元分成30元和50元，分别买3瓶和5瓶，其中3瓶送1瓶，5瓶送2瓶，共得到11瓶。/* CCF201709-1 打酱油 */ #include const int ONE = 1;const int TWO = 2;const int FIVE = 5;const int THREE = 3;const int PRICE = 10;int main(void) int n, group1, group2, group3; scanf(%d, &n); group1 = n / PRICE / FIVE; group2 = (n - group1 * PRICE * FIVE) / PRICE / THREE; group3 = (n - group1 * PRICE * FIVE - group2 * PRICE * THREE) / PRICE; printf(%dn, group1 * (FIVE + TWO) + group2 * (THREE + ONE) + group3); return 0;8.问题描述（钥匙盒）有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？输入格式输入的第一行包含两个整数N, K。接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。保证输入数据满足输入格式，你不用检查数据合法性。输出格式输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。样例输入5 24 3 32 2 7样例输出1 4 3 2 5样例说明第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。每个关键时刻后的钥匙状态如下（X表示空）：时刻2后为1X345；时刻3后为1X3X5；时刻6后为143X5；时刻9后为14325。样例输入5 71 1 143 3 121 15 122 7 203 18 124 21 195 30 9样例输出1 2 3 5 4评测用例规模与约定对于30%的评测用例，1 N, K 10, 1 w N, 1 s, c 30；对于60%的评测用例，1 N, K 50，1 w N，1 s 300，1 c 50；对于所有评测用例，1 N, K 1000，1 w N，1 s 10000，1 c 100。问题分析： 这是一个模拟题，关键在于数据表示。 对于输入的整数w,s,c，其实包含有借与还的信息，借的时间点已经明确给出，还的时间点需要计算一下。也可以说，每个数据包含有2个操作。 将操作按照题意给出的操作顺序，加入优先队列中，自然实现了操作的排队。/* CCF201709-2 公共钥匙盒 */ #include #include #include /#define DEBUGusing namespace std;struct _node int num; / 钥匙号 char op; / 操作：G-取钥匙，R-还钥匙 int time; / 时间点 bool operator a.time; else if(op != a.op) return op a.num; ;const int N = 1000;int hookN+1;int main() int n, k; int w, s, c; priority_queue q; _node t; scanf(%d%d, &n, &k); for(int i=1; i=n; i+) hooki = i;#ifdef DEBUG printf(status: ); for(int i=1; i=n; i+) printf(%d, hooki); printf(n);#endif for(int i=1; i=k; i+) scanf(%d%d%d, &w, &s, &c); t.num = w; t.time = s; t.op = G; q.push(t); t.op = R; t.time = s + c; q.push(t); while(!q.empty() t = q.top(); q.pop(); if(t.op = G) for(int i=1; i=n; i+) if(hooki = t.num) hooki = 0; break; else / t.op = R for(int i=1; i=n; i+) if(hooki = 0) hooki = t.num; break; #ifdef DEBUG printf(status: ); for(int i=1; i=n; i+) printf(%d, hooki); printf(n);#endif for(int i=1; i=n; i+) if(i != 1) printf( ); printf(%d, hooki); printf(n); return 0; 9.问题描述（分蛋糕）小明今天生日，他有n块蛋糕要分给朋友们吃，这n块蛋糕（编号为1到n）的重量分别为a1,a2, ,an。小明想分给每个朋友至少重量为k的蛋糕。小明的朋友们已经排好队准备领蛋糕，对于每个朋友，小明总是先将自己手中编号最小的蛋糕分给他，当这个朋友所分得蛋糕的重量不到k时，再继续将剩下的蛋糕中编号最小的给他，直到小明的蛋糕分完或者这个朋友分到的蛋糕的总重量大于等于k。请问当小明的蛋糕分完时，总共有多少个朋友分到了蛋糕。输入格式输入的第一行包含了两个整数n,k，意义如上所述。第二行包含n个正整数，依次表示a1,a2, ,an。输出格式输出一个整数，表示有多少个朋友分到了蛋糕。样例输入6 92 6 5 6 3 5样例输出3样例说明第一个朋友分到了前3块蛋糕，第二个朋友分到了第4、5块蛋糕，第三个朋友分到了最后一块蛋糕。评测用例规模与约定对于所有评测用例，1 n 1000，1 k 10000，1 ai 1000。/* CCF201703-1 分蛋糕 */ #include int main(void) int n, k, count=0, val, sub=0; scanf(%d%d, &n, &k); while(n-) scanf(%d, &val); if(sub += val) = k) count+; sub = 0; if(sub 0) count+; printf(%dn, count); return 0;10.问题描述（学生排队）体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。例如，下面给出了一组移动的例子，例子中学生的人数为8人。0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。输入格式输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。第二行包含一个整数m，表示调整的次数。接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。输出格式输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。样例输入833 28 -33 -2样例输出1 2 4 3 5 8 6 7评测用例规模与约定对于所有评测用例，1 n 1000，1 m 1000，所有移动均合法。问题分析：程序说明： 方法一： 数组sno2pos用于存储各个学生（学号）所在的位置；数组pos2sno是索引，pos2snoi=s表示学生s位于位置i。这个程序应该是最快速的版本。 方法二： 数组pos2sno用于存储各个所在的位置上的学生（学号），pos2snoi=s表示学生s位于位置i。这个方法是直接进行模拟。其缺点是每次需要找到指定学生（学号）的位置，顺序查找需要花费时间；优点是逻辑相对简单并且易于理解。 方法三： 使用链表来实现，是一种最容易想到的方法。这个程序的关键是如何使用STL的list（链表）实现模拟。 程序中的28-33行，有关迭代器指针移动的逻辑是不是可以改进？ 方法四： 使用STL的向量vector来实现。实际上是一种代码最为简洁的做法。 需要注意的是下标运算逻辑。 以上几种做法中，从得分考虑则推荐方法二，从时空考虑推荐方法一。其他则是使用STL实现的方法，也值得考虑。/* CCF201703-2 学生排队 */ #include #include using namespace std;vector v;int find(int x) int ret = - 1; for(int i = 0; i n m; / 初始化 for(int i=1; i=n; i+) v.push_back(i); / 模拟移动过程 for(int i=1; i p q; int pos = find(p); v.insert(v.begin() + pos + (q 0 ? q + 1 : q), p); v.erase(v.begin() + pos + (q 0 ? 1 : 0); / 输出结果 cout v0; for(int i = 1; i (int)v.size(); i+) cout vi; cout endl; return 0;11.问题描述（中间数）在一个整数序列a1,a2, ,an中，如果存在某个数，大于它的整数数量等于小于它的整数数量，则称其为中间数。在一个序列中，可能存在多个下标不相同的中间数，这些中间数的值是相同的。给定一个整数序列，请找出这个整数序列的中间数的值。输入格式输入的第一行包含了一个整数n，表示整数序列中数的个数。第二行包含n个正整数，依次表示a1,a2, ,an。输出格式如果约定序列的中间数存在，则输出中间数的值，否则输出-1表示不存在中间数。样例输入62 6 5 6 3 5样例输出5样例说明比5小的数有2个，比5大的数也有2个。样例输入43 4 6 7样例输出-1样例说明在序列中的4个数都不满足中间数的定义。样例输入53 4 6 6 7样例输出-1样例说明在序列中的5个数都不满足中间数的定义。评测用例规模与约定对于所有评测用例，1 n 1000，1 ai 1000。问题描述： 首先输入正整数n，接着输入n个正整数，如果存在一个数，比该数大或比该数小的数则输出该数，如果不存在则输出-1。问题分析： 这个问题可以用排序来解决，这是基础。可以证明，如果存在答案则必定所有数排序后的中间位置。 排序方法上有以下几种： 1.对n个数进行排序，找出中间那个数，然后将中间那个数的左右与其相等的数去掉，看左右剩下的数个数是否相等，如果相等则中间那个数就是答案，否在输出-1。 2.使用分治法，按照快速排序的基本思想来处理，只需要将中间的那个数找到即可。 3.使用STL的map类对数据进行排序。这种方法在同值的数据比较多时候，存储上会节省一些。 4.按照桶排序的基本思想，将相同的值放入同一个桶中，即对同值数据进行计数，然后再计算中间值。程序说明： 方法一： STL的algorithm中封装了许多算法，排序函数sort()其中之一，使用起来非常简单。 使用函数lower_bound()和upper_bound()来实现的话，代码会更加简单，后文也给出了这种版本的代码。数据必须在排序之后才能使用这两个函数。 这里给出了2个程序，可以比较着来看。/* CCF201612-1 中间数 */ #include #include using namespace std;const int N = 1000;int valN;int main() int n, mid, leftcount, rightcount; / 输入数据 cin n; for(int i=0; i vali; / 排序 sort(val, val+n); / 找出中间数 mid = n / 2; leftcount = mid; rightcount = n - mid - 1; / 去掉左边与中间相同值数的个数 for(int i=mid-1; i=0; i-) if(vali = valmid) leftcount-; else break; / 去掉右边与中间相同值数的个数 for(int i=mid+1; in; i+) if(vali = valmid) rightcount-; else break; / 输出结果 if(leftcount = rightcount) cout valmid endl; else cout -1 endl; return 0;12.问题描述小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资（扣除五险一金后、未扣税前的