C语言算法题
题目一
【背景】
加速度计是测量加速度的仪表。加速度测量是工程技术提出的重要课题。
要知道各瞬时飞机、火箭和舰艇所在的空间位置，可通过惯性导航系统连续地测出其加速度，然后经过积分运算得到速度分量，再次积分得到一个方向的位置坐标信号，而三个坐标方向的仪器测量结果就综合出运动曲线并给出每瞬时航行器所在的空间位置。
再如某些控制系统中，常需要加速度信号作为产生控制作用所需的信息的一部分，这里也出现连续地测量加速度的问题。能连续地给出加速度信号的装置称为加速度传感器。
但是，加速度计并非每一次传回的数值都是准确且稳定的，我们需要进行"滤波”，即人为地过滤掉显然错误的数据。
【题目】
给定一个长度为n的数组，即加速度计周期性发出的连续的n组数据。已知加速度计发出的每一个数据都可正可负。你的任务是:在这组数据中找出一个子列(即从长度为n的数组中任意截取连续的一段作为新的数组)，使得这个子列的和最大。
输入
第一行是一个整数n表示加速度计发出的数据长度第二行是n个用空格分开的整数，表示加速度计的数据
输出
一行一个整数，表示最大子列和
样例
输入
5
1 -1 1 -1 1
输出
1
输入
6
-1 3 -2 4 5 -6
输出
10
提示
对于50%的数据，1<=n<=500
对于70%的数据，1<=n<=5000
对于100%的数据，1<=n<=500000、1<=|a[i] <=100
对于第一个样例:
最大子列和为1或1+(-1)+1=1或1+(-1)+1+(-1)+1=1对于第二个样例:
最大子列和为3+(-2)+4+5=10
没有其他的方案能产生更大的子列和
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int n;
int sum = 0, maxsum = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int v;
scanf("%d", &v);
sum += v;
if (sum > maxsum) {
maxsum = sum;
} else if (sum < 0) {
sum = 0;
}
}
printf("%d\n", maxsum);
return 0;
}
题目二
东道主让现场所有的n名步兵围成一个圆圈，并声明以下规则:1号位置的步兵击杀2号位置的步兵，3号位置的步兵击杀4号位置的步兵，5号位置的步兵击杀6号位置的步兵…以此类推,直到最后只剩下一名步兵。
然而自诩南航长空御风战队最优秀的机器人，我们的步兵将这次的游戏看成了对他的一次试炼。他并不想被任何步兵所杀死，因为这样会让他感到丢脸，以至于当场爆炸。长空御风的队员们并不想在上赛场之前就失去这样一名优秀的战斗力，因此我们需要在步兵围成圆圈之前，为他找到一个合适的位置，使得我们的步兵能够成为最后一个剩下的步兵。
输入
一个整数n,表示前来交流的步兵数目。
输出
一个整数p，表示最后一个剩下的步兵的位置。
样例
输入
6
输出
5
输入
10
输出
5
输入
128
输出
1
提示
对于70%的数据，1<=n<=1000000对于30%的数据，1<=n<=1000000000
对于第一个样例，每次剩下的步兵的位置编号应发生如下变化:
1 2 3 4 5 6
1 3456
1 3 56
1 3 5
1 5
5
因此输出为5
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
int josephus(int n, int k) {
int ans = n * k;
int cnt = 1;
int tmp;
while (ans > n) {
int t1 = cnt / (k - 1);
int t2 = cnt % (k - 1);
if (ans % k > t2) {
tmp = ans - (k * t1) - t2;
} else {
int res = ans % k + (k - 1) - t2;
tmp = (ans - ans % k) - (k * (t1 + 1)) + res;
}
cnt = cnt + ceil((ans - 1) / k) - ceil((tmp - 1) / k);
ans = tmp;
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
printf("%d\n", josephus(n, 2));
return 0;
}
题目3
2021 RoboMaster机甲大师超级对抗赛中部区域赛比赛场地设立在浙江省杭州市湖州街51号浙江大学城市学院。
比赛现场共设置有把长椅，题目假设每把长椅上可以坐下的人数无上限。由于一部分观众就是城市学院的学生，因此在校外观众入场之前，第i把长椅上已经坐下了a[1]个人。现在，会新来m位校外观众，这m个人每人都会随机找一把长椅并坐下。
由于新冠疫情的影响，举办方并不希望存在一把长椅坐下了太多的人。因此，举办方找到了你，希望你帮忙求出:在已经就坐的人不改变座位的条件下，新来了m个人之后，人数最多的那把长椅上最少可能会有多少人?最多可能会有多少人?
输入
第一行为1个整数n，表示有n把长椅第二行为1个整数m，表示会新来m个人
第三行为用空格隔开的a[2]，表示第i把长椅上最初有a[i]个人
输出
一行两个整数，分别表示来了m个人之后，人数最多的那把长椅上最少会有的人数、最多会有的人数。
样例
输入
4
6
1 1 1 1
输出
3 7
输入
10
10
7612410 5 183
输出
10 20
提示
对于40%的数据，1<=n,m<=5000
对于20%的数据，1<=n,m<=50000
对于40%的数据，1<=n,m<=500000
对于100%的数据，1<=a[i]<=500
对于第一个样例，如下是所有的不考虑椅子顺序让人数最多的椅子上人数最少的座位方案:
3331
3322
不会再有其他的方案使得人数最多的那把椅子上人数最少。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int n = 0;
int m = 0;
int chair[50000] = { 0 };
int len = 0;
int comp(const int* a, const int* b) {
return (*a > *b);
}
int main() {
scanf("%d", &n);
scanf("%d", &m);
for (int i = 0; i < n; i++) {
scanf("%d", &chair[len++]);
}
qsort( chair, len, sizeof(chair[0]), comp);
int mx = 0;
mx = chair[ len - 1] + m;
int mn = 0;
int remain = m;
int the_max = chair[ len - 1];
int sum = 0;
for (int i = 0; i < len; i++) {
sum = sum + (the_max - chair[i]);
}
if (sum <= m) {
int yushu = (m - sum) % len;
if (yushu == 0) {
mn = the_max + (m - sum) / len;
} else {
mn = the_max + (m - sum) / len + 1;
}
} else {
mn = the_max;
}
printf("%d %d", mn, mx);
return 0;
}
题目4
输入
第一行为两个用空格隔开的整数n m
接下来n行，每行m个数字，用空格隔开，仅为0(白色)或1(黑色)。
输出
一行一个整数，为最大黑色正方形的边长。
样例
输入
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出
2
输入
6 9
1 0 1 1 1 1 1 1 1
1 1 0 0 0 0 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 1 1 1 0 0 0
1 0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0
输出
3
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int matrix[1000][1000] = { 0 };
int temp[1000][1000] = { 0 };
int min(int a, int b) {
return (a < b) ? a : b;
}
int side() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &matrix[i][j]);
}
}
for (int i = 0; i < n; ++i) {
temp[i][0] = matrix[i][0];
}
for (int j = 0; j < m; ++j) {
temp[0][j] = matrix[0][j];
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
if (matrix[i][j] == 1) {
temp[i][j] = min(min(temp[i - 1][j], temp[i][j - 1]), temp[i - 1][j - 1]) + 1;
}
if (matrix[i][j] == 0) {
temp[i][j] = 0;
}
}
}
int max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (temp[i][j] > max) {
max = temp[i][j];
}
}
}
return max;
}
int main() {
printf("%d\n", side());
return 0;
}
|