# NENUOJ 之 算法1第7章
# 前言
第7、8、9章是排序、模拟和高精度，因为笔者精力有限，这里的题解采用GPT的辅助。
# 7001 中位数 (opens new window)
# 题目描述
给定一个由N个非负整数构成的序列，我们来定义一下序列的中位数，如果N是奇数，在对序列排序后，中位数就是最中间的那个数，即排序后，中位数的位置为(N+1)/2，这里序列的位置从1开始。如果N是偶数，则中位数为排序后中间两个数和的一半，即N/2和(N/2)+1处。但是需要注意的是原始序列可能是未排序的。 你的任务就是编程找出给定序列中的中位数。
# 输入
测试有多组数据，每组数据第一行只有一个整数N，表示序列的长度。接下来就是N个数，每个数占一行，序列的长度范围为1到250000。序列中的每个数都是不超过2^32-1（包括它）的正整数。
# 输出
输出中位数，保留小数点后一位。
# 样例输入 复制
4 3 6 4 5# 样例输出 复制
4.5
# 思路：
排个序，然后找中间的就可以了。奇偶不同很容易看出来，分类讨论一下即可。
# 代码C语言：
#include <stdio.h>
#include <stdlib.h>
const int MAXN = 250000;
//比较函数
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
//计算中位数
double find(int nums[],int n) {
qsort(nums,n,sizeof(int),compare);
//如果序列长度为奇数
if (n % 2 != 0) {
return nums[n / 2];
}
//如果序列长度为偶数
else {
return (nums[n / 2 - 1] + nums[n / 2]) / 2.0;
}
}
int main() {
int n;
int nums[MAXN];
while(~scanf("%d", &n)) {
for (int i = 0;i < n;i++) {
scanf("%d",&nums[i]);
}
double median = find(nums,n);
printf("%.1f\n",median);
}
return 0;
}
# 7002 猜数游戏 (opens new window)
# 题目描述
Stan和Ollie在玩一个猜数游戏。先由Stan想出一个1到10之间的数，Ollie猜这个数可能是几。Ollie每猜一个数，Stan回答这个数比原数高、低，还是正确，对应的回答为“too high”，“ too low”，“right on”。猜数正确后，此轮游戏结束。每次游戏结束，Ollie判断是不是Stan说谎。如果是，则输出“Stan is dishonest”，否则，输出“Stan may be honest”。
# 输入
请在这里写输入格式。例如：输入在一行中给出2个绝对值不超过1000的整数A和B。有多组数据，输入一个整数n（1 <= n <= 10）。接下来的一行是（too high，too low，right on）中的一个。如果是right on，则这组输入结束。如果n=0，表示这是最后一组数据。
# 输出
Stan没有说谎，则输出“Stan may be honest”，否则输出“Stan is dishonest”。
# 样例输入 复制
10 too high 3 too low 4 too high 2 right on 5 too low 7 too high 6 right on 0
# 代码C语言：
#include<stdio.h>
#include<string.h>
int main(){
char str1[1000];
char str2[1000];
int n;
int res = 0;
int temp = 0;
int a[100] = {0};
while(~scanf("%d",&n)){
if(n == 0) break;
scanf("%s %s",str1,str2);
if(strcmp(str1,"too") == 0){
//too high
if(strcmp(str2,"high") == 0){
for(int i = n;i <= 10;i++){
a[i] = 1;
}
}
//too low
if(strcmp(str2,"low") == 0){
for(int i = 1;i <= n;i++){
a[i] = 1;
}
}
}
if(strcmp(str1,"right") == 0){
if(a[n] == 0){
printf("Stan may be honest\n");
}else{
printf("Stan is dishonest\n");
}
for(i = 1;i <= 10;i++){
a[i] = 0;
}
}
}
return 0;
}
# 7003 组合锁 (opens new window)
# 题目描述
现在周小小开学了。他们寝室被一密码锁（见图所示）锁住了。他知道密码为三对数，如36-23-12，同时知道开锁的方法。其方法： （1）先顺时针转两圈。 （2）逆时针转到第一个数的位置。 （3）逆时针转一圈。 （4）顺时针旋转到第二个数。 （5）指针又逆时针转到第三个数。 已知指针的初始位置和密码，问转多少度才能开锁。
# 输入
有多组数据，每组数据含有四个数，分别是n,fisrt,middle,last，均是小于40（n为起始位置）大于0的。当输入是“0 0 0 0”时，结束。
# 输出
输出所要转的度数。
# 样例输入 复制
0 30 0 30 5 35 5 35 0 20 0 20 7 27 7 27 0 10 0 10 9 19 9 19 0 0 0 0# 样例输出 复制
1350 1350 1620 1620 1890 1890
# 思路：
记住数字是0 ~ 40，然后模拟即可，注意每次旋转的角度。总共40格，一格就是9度。
# 代码C++：
#include<bits/stdc++.h>
int addi(int a,int b){
return a < b ? 40 + a - b : a - b;
}
int main(){
int n,first,middle,last;
while(std::cin >> n >> first >> middle >> last){
int sum = 0;
if(n == 0 && first == 0 && middle == 0 && last == 0) break;
sum += 720;
sum += addi(n,first) * 9;
sum += 360;
sum += (40 - addi(first,middle)) * 9;
sum += addi(middle,last) * 9;
std:: cout << sum << endl;
}
return 0;
}
# 代码C语言：
#include <stdio.h>
//计算转动的度数
int cal(int n,int first,int middle,int last) {
int total = 0;
//顺时针转两圈
total += 720;
//逆时针转到第一个数的位置
total += (n < first ? 40 + n - first : n - first) * 9;
//逆时针转一圈
total += 360;
//顺时针旋转到第二个数
total += (40 - (first < middle ? 40 + first - middle : first - middle)) * 9;
//指针又逆时针转到第三个数
total += (middle < last ? 40 + middle - last : middle - last) * 9;
return total;
}
int main() {
int n,first,middle,last;
while (~scanf("%d %d %d %d",&n,&first,&middle,&last)) {
if (!n && !first && !middle && !last) break;
int degrees = cal(n,first,middle,last);
printf("%d\n",degrees);
}
return 0;
}
# 7004 ACM排名 (opens new window)
# 题目描述
ACM比赛是由一款特殊的软件支撑的。这个软件其中的一个功能就是执行一项工作接受和评价队伍的运行结果，并且把结果显示在排名表中。排名规则如下： （1） 每次运行的结果要不是接受要不就是拒绝。 （2） 任何一个运行中的被接受的结果都被认为是这个队伍的。 （3） 一个被解决过问题的总耗时包括两个部分，一是从比赛开始到提交通过时的时间，二是每次提交没有通过增加20分钟罚时。对于未解决的问题是不计算其时间的。 （4） 每道被解决的问题的用时的和就是这个队伍的总用时。 （5） 根据解题数来决定队伍排名，解题数相同的用时少的排名靠前。 （6） 尽管显示的是分钟，但是实际上是精确到秒，秒数是要在排名时候考虑进去的。 （7） 两个队伍如果排名完全相同，则按队伍号码排序。 你的任务就是，给定N次运行，每次运行都有提交时间、运行结果，计算C个队的排名情况。
# 输入
输入包括整数C和N，接下来是N行数据，每行包括4个整数ci pi ti ri，其中ci 表示队伍号，pi表示题号，ti提交的时间（秒数），ri表示运行结果，如果结果被接受了为1，否则为0。1 ≤ C, N ≤ 1000, 1 ≤ ci ≤ C, 1 ≤ pi ≤ 20, 1 ≤ ti ≤ 36000。
# 输出
按排名先后输出C个整数。
# 样例输入 复制
3 3 1 2 3000 0 1 2 3100 1 2 1 4200 1# 样例输出 复制
2 1 3
# 思路：
这道题最大的陷阱在于有多组样例。
NENUOJ特有的德行就是题目不说多组。写了结构体的话记得初始化。这道题就是一道典型的结构体排序的题目，就是模拟每个队伍的过题数目和总时长。
- 如果提交结果为通过，则更新队伍的解题数量、总用时，并考虑罚时情况。
- 如果提交结果为未通过，则增加相应题目的罚时。
理论上要考虑一件事，即重复通过的题目不能再通过，即代码二考虑的情况：要先按时间排序，然后再考虑。
所以代码一虽然能通过，但其实有很多问题【无法通过POJ的检测】。
# 代码C++ 代码一：
#include<bits/stdc++.h>
using namespace std;
int c,n;
struct group//每个队的情况
{
int no;//队伍号码
int solved;//队伍过题数
int time;//总用时
int penalty[21];//每道题的罚时
};
bool cmp(group x,group y)
{
if(x.solved != y.solved) return x.solved > y.solved;//过题多的排前面
if(x.time != y.time) return x.time < y.time;//过题相同，用时少的排前面
return x.no < y.no;//两个都相同，号码小的排前面
}
void solve()
{
vector<group> rank(c + 1);// 开c + 1 大小的group数组用来存c个队
for (int i = 1; i <= c; i++) {//初始化
rank[i].no = i;
rank[i].solved = 0;
rank[i].time = 0;
}
int ci,pi,ti,ri;
for(int i = 1; i <= n; i++)
{
cin >> ci >> pi >> ti >> ri;
if(ri)
{
rank[ci].solved++;
//如果有这题罚时，把罚时加上
if(rank[ci].penalty[pi] > 0) rank[ci].time += rank[ci].penalty[pi];
//加上过题的时间
rank[ci].time += ti;
}
else
{
//答案错误，这一题增加罚时
rank[ci].penalty[pi] += 1200;
}
}
//对c个队伍排名排序
sort(rank.begin() + 1, rank.begin() + 1 + c, cmp);
//输出答案
for(int i = 1; i <= c; i++)
{
cout << rank[i].no << " ";
}
}
int main()
{
while(cin >> c >> n){
solve();
cout << endl;
}
}
# 代码C语言 代码二：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct group {
int no; // 队伍号码
int solved; // 队伍解决的题目数量
int time; // 总用时
int penalty[21]; // 每道题的罚时
int solvedProblems[21]; // 标记是否已解决
};
struct submission {
int ci, pi, ti, ri;
};
// 提交的比较函数，用于按时间顺序排序
int cmpSubmissions(const void *a, const void *b) {
struct submission *subA = (struct submission *)a;
struct submission *subB = (struct submission *)b;
return subA->ti - subB->ti;
}
// 队伍的比较函数，用于排名
int cmp(const void *a, const void *b) {
struct group *g1 = (struct group *)a;
struct group *g2 = (struct group *)b;
if (g1->solved != g2->solved) return g2->solved - g1->solved;
if (g1->time != g2->time) return g1->time - g2->time;
return g1->no - g2->no;
}
int main() {
int c, n;
while (~scanf("%d %d", &c, &n)) {
struct group rank[1005];
struct submission subs[1005];
// 初始化队伍信息
for (int i = 1; i <= c; i++) {
rank[i].no = i;
rank[i].solved = 0;
rank[i].time = 0;
memset(rank[i].penalty, 0, sizeof(rank[i].penalty));
memset(rank[i].solvedProblems, 0, sizeof(rank[i].solvedProblems));
}
// 读取提交记录
for (int i = 1; i <= n; i++) {
scanf("%d %d %d %d", &subs[i].ci, &subs[i].pi, &subs[i].ti, &subs[i].ri);
}
// 对提交记录按时间顺序排序
qsort(subs + 1, n, sizeof(struct submission), cmpSubmissions);
// 处理提交记录，更新队伍状态
for (int i = 1; i <= n; i++) {
int ci = subs[i].ci;
int pi = subs[i].pi;
int ti = subs[i].ti;
int ri = subs[i].ri;
if (!rank[ci].solvedProblems[pi]) {
if (ri) {
rank[ci].solved++;
rank[ci].time += ti + rank[ci].penalty[pi];
rank[ci].solvedProblems[pi] = 1;
} else {
rank[ci].penalty[pi] += 1200;
}
}
}
// 对队伍进行排名排序
qsort(rank + 1, c, sizeof(struct group), cmp);
// 输出排名结果
for (int i = 1; i <= c; i++) {
printf("%d ", rank[i].no);
}
printf("\n");
}
return 0;
}