C/C++编程三级 题库
胖达与盆盆奶
大熊猫,俗称“胖达”,会排队吃盆盆奶。它们能和谐吃奶的前提,是它们认为盆盆奶的分配是“公平”的,即:更胖的胖达能吃到更多的奶,等胖的胖达得吃到一样多的奶。另一方面,因为它们是排好队的,所以每只胖达只能看到身边胖达的奶有多少,如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶,当另一份盆盆奶多出至少 100 毫升的时候,它们才能感觉到是“更多”了,否则没感觉。
现在给定一排胖达的体重,请你帮饲养员计算一下,在保持给定队形的前提下,至少应该准备多少毫升的盆盆奶?
时间限制:6000
内存限制:65535
输入
输入首先在第一行给出正整数 n(≤ 104),为胖达的个数。随后一行给出 n 个正整数,表示 n 只胖达的体重(公斤)。每个数值是不超过 200 的正整数,数字间以空格分隔。
输出
在一行中输出至少应该准备多少毫升的盆盆奶。
样例输入
10 180 160 100 150 145 142 138 138 138 140
样例输出
3000
提示
样例解释: 盆盆奶的分配量顺序为: 400 300 200 500 400 300 200 200 200 300
//参考代码1 C++
#include <iostream>
using namespace std;
int n, ans, A[10005], L[10005], R[10005];
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i < n; i++) {
int j = i;
while(j + 1 <= n && A[j] >= A[j + 1]) {
if (A[j] > A[j + 1]) ++L[i];
++j;
}
}
for (int i = n; i > 1; i--) {
int j = i;
while(j - 1 >= 1 && A[j] >= A[j - 1]) {
if (A[j] > A[j - 1]) ++R[i];
--j;
}
}
for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;
cout << ans;
return 0;
}//参考代码2 C语言
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, ans = 0;
int A[10005], L[10005] = {0}, R[10005] = {0};
// 读取胖达的个数
scanf("%d", &n);
// 读取每只胖达的体重
for (int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
// 计算 L 数组
for (int i = 1; i < n; i++) {
int j = i;
while (j + 1 <= n && A[j] >= A[j + 1]) {
if (A[j] > A[j + 1]) ++L[i];
++j;
}
}
// 计算 R 数组
for (int i = n; i > 1; i--) {
int j = i;
while (j - 1 >= 1 && A[j] >= A[j - 1]) {
if (A[j] > A[j - 1]) ++R[i];
--j;
}
}
// 计算总量
for (int i = 1; i <= n; i++) {
ans += max(L[i], R[i]) * 100 + 200;
}
// 输出结果
printf("%d\n", ans);
return 0;
}三足鼎立
当三个国家中的任何两国实力之和都大于第三国的时候,这三个国家互相结盟就呈“三足鼎立”之势,这种状态是最稳定的。
现已知本国的实力值,又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟,以成三足鼎立。有多少种选择呢?
时间限制:10000
内存限制:65536
输入
输入首先在第一行给出 2 个正整数 n(2 ≤ n ≤ 105)和 P(≤ 109),分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数,表示n 个其他国家的实力值。每个数值不超过 109,数字间以空格分隔。
输出
在一行中输出本国结盟选择的个数。
样例输入
7 30 42 16 2 51 92 27 35
样例输出
9
提示
样例解释: 能联合的另外 2 个国家的 9 种选择分别为: {16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。
//参考代码1 C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, p;
int a[N];
ll s;
int main() {
cin >> n >> p;
for (int i = 1; i <= n; i ++)
cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i ++) {
int l = i + 1, r = n;
int minn = abs(a[i]-p), maxx = a[i] + p;
int n1, n2; // 记录下标
if (l>r) break;
while (l <= r) { // 找到大于最小值的数
int mid = (l + r) / 2;
if (a[mid] <= minn)
l = mid + 1;
else
r = mid - 1;
}
n1 = l;
l = i + 1, r = n;
while (l <= r) { // 找到小于最大值的数
int mid = (l + r) / 2;
if (a[mid] < maxx)
l = mid + 1;
else
r = mid - 1;
}
n2 = r;
s += (n2 - n1) + 1;
}
cout << s;
return 0;
}//参考代码2 C语言
#include <stdio.h>
#include <stdlib.h>
long long n, x, cnt;
int a[100005];
int cmpfunc(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int upper_bound(int arr[], int n, int x) {
int l = 0;
int r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] <= x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int lower_bound(int arr[], int n, int x) {
int l = 0;
int r = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
int main() {
scanf("%lld %lld", &n, &x);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmpfunc);
for (int i = 0; i < n - 1; ++i) {
int l, r;
if (a[i] < x) {
l = upper_bound(a + i + 1, n - i - 1, x - a[i]);
} else {
l = upper_bound(a + i + 1, n - i - 1, a[i] - x);
}
r = lower_bound(a + i + 1, n - i - 1, a[i] + x) - 1;
if (l == n - i - 1) {
continue;
}
cnt += (r - l + 1);
}
printf("%lld\n", cnt);
return 0;
}最近的斐波那契数
斐波那契数列 Fn 的定义为:对 n ≥ 0 有 Fn+2 = Fn+1 + Fn,初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。
本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。
时间限制:1000
内存限制:65536
输入
输入在一行中给出一个正整数 N(≤ 108)。
输出
在一行输出与 N 最近的斐波那契数。如果解不唯一,输出最小的那个数。
样例输入
305
样例输出
233
提示
样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72,则应输出较小的那个解。
#include<iostream>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main(){
int n[101];
n[0]=0,n[1]=1;
for(int i=2;i<43;i++){
n[i]=n[i-1]+n[i-2];
}
int N;
cin>>N;
int min_diff=9999999;
int temp[101]={0},j=0;
for(int i=0;i<43;i++){
if(abs(n[i]-N)<min_diff){
min_diff=abs(n[i]-N);
temp[j++]=n[i];
}
}
cout<<temp[j-1];
return 0;
}构造性证明
关于数学定理证明,也有高下之分。最暴力的证明方法是“构造性证明”,即当需要证明某种解存在时,直接把解构造出来,而不是仅通过推理证明解之存在。
下面有一个定理:
设 ai(i=1, … , 5)均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l,使得 |ai / aj - ak / al| < 1/2。
作为程序员,就请你编写程序构造出正确的下标,验证这个结论。
时间限制:1000
内存限制:65536
输入
输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出,我们令输入的数字在 [10-10, 1010] 区间内,且小数点后不超过 10 位小数。
输出
在一行中首先输出使得定理结论成立的下标有多少套,随后输出最小的一套下标。数字间以 1 个空格分隔,行首尾不得有多余空格。 注:所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4},是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立,且 ik < jk。
样例输入
3.12 5.27 0.0007 9825.4413 10
样例输出
18 1 4 3 2
提示
样例解释: 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个,例如 5、4、3、2 就是另一套解。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const double EPS = 1e-9;
// 比较两个双精度浮点数是否相等(考虑精度误差)
bool doubleEqual(double a, double b) {
return fabs(a - b) < EPS;
}
int main() {
vector<double> nums(5);
for (int i = 0; i < 5; ++i) {
cin >> nums[i];
}
int count = 0;
vector<int> result(4);
// 四重循环遍历所有可能的四个下标组合
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
if (i == j) continue;
for (int k = 0; k < 5; ++k) {
if (k == i || k == j) continue;
for (int l = 0; l < 5; ++l) {
if (l == i || l == j || l == k) continue;
double val = fabs(nums[i] / nums[j] - nums[k] / nums[l]);
if (val < 0.5) {
count++;
if (count == 1) {
result = {i + 1, j + 1, k + 1, l + 1};
}
}
}
}
}
}
cout << count << " ";
for (int idx : result) {
cout << idx << " ";
}
return 0;
}环形公路出口
一条环形高速路上有 N 个出口。给定任意一对出口,请你算出这两个出口之间的最短距离。
时间限制:1000
内存限制:65536
输入
输入第一行给出区间 [3,105] 内的整数 N,以及 N 个整数距离 D1 D2 … DN,其中 Di 是第 i 和第 i+1 个出口之间的距离,DN 是第 N 和第 1 个出口之间的距离。同行数字间以空格分隔。 第二行给出正整数 M (≤ 104)。随后 M 行,每行给出一对出口的编号(出口从 1 到 N 顺序编号)。题目保证公路全长不超过 107。
输出
输出 M 行,每行给出对应输入的一对出口之间的最短距离。
样例输入
5 1 2 4 14 9 3 1 3 2 5 4 1
样例输出
3 10 7
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> distances(N);
for (int i = 0; i < N; ++i) {
cin >> distances[i];
}
vector<int> prefixSum(N + 1, 0);
for (int i = 0; i < N; ++i) {
prefixSum[i + 1] = prefixSum[i] + distances[i];
}
int M;
cin >> M;
for (int i = 0; i < M; ++i) {
int start, end;
cin >> start;
cin >> end;
if (start > end) {
swap(start, end);
}
int sum = prefixSum[end - 1] - prefixSum[start - 1];
int total = prefixSum.back();
cout << min(sum, total - sum) << endl;
}
return 0;
}拼大数
如何随机生成一个有 n 位数的大数呢?一种方法是,找到 n 个小朋友,每人发一张卡片,卡片一面写着编号(这里假设小朋友们从 1 到 n 编号),另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排,要求一张挨着一张,按他们的编号升序排列,显示他们自己写的数字。
但是,让十万个孩子都按指令行动,可太难了。结果是卡片乱七八糟满墙都是,有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8,我们应该在墙上看到 8,但是却看到了 23…… 你的任务就是把这些卡片整理好,得到我们真想要拼成的大数。
时间限制:6000
内存限制:65536
输入
输入第一行给出一个正个整数 n (≤ 105),随后 n 行,每行按 n1 n2的格式给出一张卡片两面的数字。
输出
在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数,那么就很难说哪个数字是编号,哪个数字是小朋友自己写的,所以解可能是不唯一的。这时候需要输出能得到的最小的数字。
样例输入
12 7 11 8 9 3 1 2 12 4 6 10 0 5 1 2 5 6 8 1 4 7 2 9 3
样例输出
359114268072
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> pq(n + 1);
vector<pair<int, int>> cards(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
cards[i].first = a;
cards[i].second = b;
// Check if a is a valid id and b is a valid digit
if (a >= 1 && a <= n && b >= 0 && b <= 9) {
pq[a].emplace(b, i);
}
// Check if b is a valid id and a is a valid digit
if (b >= 1 && b <= n && a >= 0 && a <= 9) {
pq[b].emplace(a, i);
}
}
vector<bool> used(n, false);
vector<int> result(n + 1, -1);
for (int i = 1; i <= n; ++i) {
while (!pq[i].empty()) {
auto [d, idx] = pq[i].top();
pq[i].pop();
if (!used[idx]) {
used[idx] = true;
result[i] = d;
break;
}
}
if (result[i] == -1) {
cout << "No solution" << endl;
return 0;
}
}爆气球
爆气球对孩子们来说是很好玩的游戏。假设有 n 只气球被布置在一条直线上,游戏的目标很简单,就是爆掉尽可能多的气球。但是这里我们加一条特殊的规则 —— 你只能跳一次。我们假设聪明的娃穿了件浑身带刺的衣服,跳到某个位置,躺平,这样气球只要碰到娃身体的任何部分都会立刻爆炸。那么你的任务就是告诉娃应该跳到哪里,才能一次爆掉最多的气球。
时间限制:4000
内存限制:262144
输入
输入第一行两个正整数:n(≤ 105)为一条线上布置的气球的数量;h(≤ 103)为孩子伸直双臂能达到的高度。第二行给出 n 个整数,每个对应一只气球在直线轴上的坐标。题目保证坐标按递增顺序给出,所有坐标值在 [-106, 106] 区间内。
输出
在一行中输出孩子跳跃的位置坐标,使得孩子跳到这个位置然后躺平能够爆掉身下最多的气球;随后输出能爆掉的气球的最大数量。如果这个坐标不唯一,输出最小的那个值。 一行中的数间应有 1 个空格。
样例输入
11 120 -120 -40 0 80 122 140 160 220 240 260 300
样例输出
120 5
提示
注意:跳到从 120 到140,或 240 到 260 之间的任何位置,都可以爆掉 5 只气球,所以 120 作为最小的坐标被输出。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 1;
int a[N];
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int y = 0;
int z = -1;
int q = 0;
for (int i = 0; i < n; i++) {
y = 0;
int t = a[i] + m;
int start = i;
while (start < n && a[start] <= t) {
if (a[start] >= a[i]) {
y++;
}
start++;
}
if (y > z) {
z = y;
q = start;
}
}
cout << a[q-1] - m << " " << z << endl;
}有多少坑
大雨过后,一些高低不平的地方就会形成积水,俗称为“坑”。这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条,测量出每个窄条的高度。假设有无穷多的水量从天而降,请你计算一下,这段路面上会形成多少个水坑?坑的最大深度是多少毫米?
时间限制:7000
内存限制:262144
输入
输入第一行给出一个正整数 N(≤ 100000)。随后一行给出 N 个非负整数,为路面横截面总左到右的单位宽度窄条的高度,以毫米为单位,不超过 1000。
输出
输出分两行,第一行输出水坑的个数,第二行输出所有水坑中最大的深度,以毫米为单位。 注意:即使两个相邻的水坑有相同高度的水平面,只要之间有窄条相隔,就算是两个水坑。
样例输入
12
1 4 2 10 7 1 2 1 8 3 1 2
样例输出
3
7
提示
样例说明: 下图给出了样例中得到的水坑示意图。

#includeusing namespace std; int a[1000000]; int main(){ int n; cin >> n; for(int i=0; i > a[i]; int left, right; //找左边围栏下标 for(left=0; left 0 && a[right]<=a[right-1]; right--);//右突起 int x, y; int cnt = 0; int mmax = 0; while(1){//从两边到中间 if(left>=right) break; x = a[left]; //会不断更新 y = a[right]; if(x mmax) mmax = x-a[left]; } if(tmp>0) cnt++;//有跨过窄条才算一个水坑 } else//左高右低,右向左走 { int tmp = 0; while(left mmax) mmax = y-a[right]; } if(tmp>0) cnt++; } } cout << cnt << endl << mmax; }
买地攻略
数码城市有土地出售。待售的土地被划分成若干块,每一块标有一个价格。这里假设每块土地只有两块相邻的土地,除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价,请你编写程序,根据客户手头的现金量,告诉客户有多少种不同的购买方案。
时间限制:8000
内存限制:262144
输入
输入首先在第一行给出两个正整数:N(≤ 104)为土地分割的块数(于是这些块从 1 到 N 顺次编号);M(≤ 109)为客户手中的现金量。 随后一行给出 N 个正整数,其中第 i 个数字就是第 i 块土地的标价。 题目保证所有土地的总价不超过 109。
输出
在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
样例输入
5 85 38 42 15 24 9
样例输出
11
提示
样例解释: 这 11 种不同的方案为: 38 42 15 24 9 38 42 42 15 42 15 24 15 24 15 24 9 24 9
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
int res = 0;
cin >> n >> k;
int arr[n+1];
int num;
arr[0] = 0;
for(int i = 1;i <= n;++i)
{
cin >> num;
arr[i] = arr[i-1] + num;
}
for(int i = 1;i <= n;++i)
{
for(int j = i;j <= n;++j)
{
if(arr[j] - arr[i-1] <= k) ++res;
else break;
}
}
cout << res;
}画作
题目描述
墙上,挂着一幅由 n×n 个彩色方格组成的画作。画作的内容可以用一个 n×n 的字符矩阵来表示。
现在想要将这幅画顺时针旋转 90 度后重新悬挂,请你他计算出旋转后的画作是什么样的。
输入格式
第一行,一个整数表示 n
接下来 n 行,每行 n 个字符。
输出格式
输出 n 行,每行 n 个字符,表示顺时针旋转 90 度后的矩阵。
输入样例#1
4 ooxx xoox xxxx xxxx
输出样例#1
xxxo xxoo xxox xxxx
输入样例#2
2 12 34
输出样例#2
31 42
说明提示
1≤n≤1000
//参考代码1
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 1005;
char mat[MAXN][MAXN];
char res[MAXN][MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); // 加速输入输出,n=1000必加
int n;
cin >> n;
// 读取原图
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++)
{
mat[i][j] = s[j];
}
}
// 顺时针90度旋转赋值
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
res[j][n - 1 - i] = mat[i][j];
}
}
// 输出结果
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << res[i][j];
}
cout << '\n';
}
return 0;
}//参考代码2
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
char mat[MAXN][MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++)
mat[i][j] = s[j];
}
// 1. 上下翻转
for (int i = 0; i < n / 2; i++)
{
for (int j = 0; j < n; j++)
swap(mat[i][j], mat[n - 1 - i][j]);
}
// 2. 主对角线交换
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
swap(mat[i][j], mat[j][i]);
}
// 输出
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << mat[i][j];
cout << '\n';
}
return 0;
}花坛
题目描述
花坛里有 n 朵花,每朵花的编号为 1,2,…,n。初始时,所有花的高度都是 0。
现在给定一个数列 h={h1,h2,…,hn},你可以重复进行如下的浇水操作,每次操作:任选一段连续区间 [l,r],区间内每朵花高度加 1。可以无限重复该操作,使得第 k 朵花的最终高度恰好为 hk(1≤k≤n)。
求完成目标需要的最小操作浇水次数。
输入格式
第一行一个整数,表示花的数量 n
第二行 n 个整数,依次表示每朵花需要达到的目标高度 h1,h2,…,hn
输出格式
输出一个整数,表示达成目标所需的最少浇水操作次数。
输入样例#1
5 3 1 2 3 1
输出样例#1
5
输入样例#2
8 4 23 75 0 23 96 50 100
输出样例#2
221
说明提示
1≤n≤100
0≤hi≤100
所有输入均为整数
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int h[105];
for (int i = 0; i < n; i++)
{
cin >> h[i];
}
int ans = h[0];
for (int i = 1; i < n; i++)
{
int diff = h[i] - h[i - 1];
if (diff > 0)
ans += diff;
}
cout << ans << endl;
return 0;
}排队名单
题目描述
火车站的售票大厅中有 n 个售票窗口(窗口编号为1,...,n),春运大潮来了,今天窗口还没有开放人们就已经陆陆续续涌进来。
现在按顺序告诉你涌进来的 m 个人的目标窗口和排队编号(为 1,...,m),请你输出售票前各窗口的排队情况。
输入
第一行两个正整数 n、m。
之后 m 个整数 ai,表示第 i 个进来的人到 ai 窗口排队。
输出
n 行,每行若干整数,分别第 i 个窗口前,从前到后排队人的编号,如果该窗口没人排,请输出 nobody。
数据范围:1≤n≤10^4,1≤m≤10^7,1≤ai≤n。
输入样例1
3 7 2 3 1 3 1 1 1
输出样例1
3 5 6 7 1 2 4
输入样例2
7 4 1 3 3 6
输出样例2
1 nobody 2 3 nobody nobody 4 nobody
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n);
for (int i = 0; i < m; i++) {
int k;
cin >> k;
if (k >= 1 && k <= n)
a[k-1].push_back(i+1);
}
for (int i = 0; i < n; i++) {
if (a[i].empty()) {
cout << "nobody\n";
} else {
for (size_t j = 0; j < a[i].size(); j++) {
if (j > 0) cout << " ";
cout << a[i][j];
}
cout << "\n";
}
}
return 0;
}移动距离
森林里住着 26 只小动物,它们分别对应字母 A 到 Z。这些小动物的家沿着一条直线排列,相邻两家之间的距离为 1。它们的排列顺序记作一个字符串 S。
现在,你要按顺序去拜访 A、B、C、……、Z。每次拜访时,你需要从当前动物的家移动到目标小动物的家。起初,你直接在动物 A 所处的位置。请计算到拜访完Z为止,需要移动的距离之和。
时间限制:1000ms,内存限制:256MB
输入格式
共一行,输入一串字符串 S。
输出格式
共一行,输出一个整数,表示从 A 出发到拜访完 Z 的最小总移动距离。
输入样例#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
输出样例#1
25
输入样例#2
VENFLQURTCWOAXMGJYIZDKSBHP
输出样例#2
231
数据范围:
S长度为 26。
#include <stdio.h>
#include <math.h>
int main() {
char s[27]; // 存储输入的字符串(长度固定为26)
scanf("%s", s);
int pos[26]; // 记录每个字母的位置,索引 0对应 A,25 对应 Z
for (int i = 0; i < 26; i++) {
pos[s[i] - 'A'] = i;
}
int total = 0;
int cur = pos[0]; // 初始位置是 A 的位置(pos[0])
// 按顺序从 A 到 Z 计算移动距离
for (int i = 1; i < 26; i++) {
int tag = pos[i];
total += abs(tag - cur); // 累加移动距离
cur = tag;
}
printf("%d\n", total);
return 0;
}最近的数
给定一个整数 X 和一个长度为 N 的整数序列 p1、p2、……、pN。请找出不在该序列中的整数(不一定为正数)中,与 X 的差的绝对值最小的那个整数。若存在多个满足条件的整数,则输出其中最小的一个。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:两个整数 X、N;
第二行:N 个整数表示 p1、p2、……、pN。
注意:当 N = 0 时,第二行为空行。
输出格式
输出满足条件的整数。
输入样例#1
6 5 4 7 10 6 5
输出样例#1
8
输入样例#2
6 5 4 7 8 6 5
输出样例#2
3
数据范围:
0≤ N < 100;1≤X、pi<100。
#include <stdio.h>
#include <math.h>
int x, n, p[100];
bool isIn(int k) {
for(int i=0; i<n; i++) {
if(p[i] == k)
return true;
}
return false;
}
int main() {
scanf("%d%d", &x, &n);
for (int i = 0; i < n; i ++) {
scanf("%d", &p[i]);
}
for(int d = 0; ; d++) {
int c = x - d; //较小的数
if(!isIn(c)) {
printf("%d\n", c);
return 0;
}
c = x + d; //较大的数
if(!isIn(c)) {
printf("%d\n", c);
return 0;
}
}
return 0;
}打印城门
题目描述
给定一个正整数 n,输出如下的星号城门。具体格式请见样例。
输入格式
第一行:单个整数 n。
输出格式
输出规模为 n 的星号城门,注意每一行的末尾不能出现空格字符。
输入样例#1
3
输出样例#1
* *** ***** ** ** *** *** **** ****
输入样例#2
5
输出样例#2
* *** ***** ******* ********* *** *** **** **** ***** ***** ****** ****** ******* *******
说明提示
1≤n≤100,保证 n 是一个奇数。
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 上半部分:三角形
for (int i = 1; i <= n; i++) {
// 打印前导空格
for (int j = 1; j <= 2*n - i; j++) {
cout << " ";
}
// 打印星号
for (int j = 1; j <= 2*i - 1; j++) {
cout << "*";
}
cout << endl;
}
// 下半部分:城门
for (int i = 1; i <= n; i++) {
// 打印前导空格
for (int j = 1; j <= n - i; j++) {
cout << " ";
}
// 计算左右星号数量(整数除法)
int stars = i + n/2;
// 打印左侧星号
for (int j = 1; j <= stars; j++) {
cout << "*";
}
// 打印中间空格
for (int j = 1; j <= n; j++) {
cout << " ";
}
// 打印右侧星号
for (int j = 1; j <= stars; j++) {
cout << "*";
}
cout << endl;
}
return 0;
}寻找页码
题目描述
几乎所有的书都会印页码,从第1页开始,页码组成的数字序列如下:
1,2,3,4,… ,10,11,12,…
现在,给定一个0到9之中的数码 a,请问,a 在这串序列中,第 k 次出现,是在哪一页上?
以数码 1 为例,第一次出现在第 1 页,第二次出现在第 10 页,第三次和第四次都出现在第 11 页上。
输入格式
第一行:两个整数 a 和 k。
输出格式
单个整数表示答案。
输入样例#1
1 5
输出样例#1
12
输入样例#2
2 23
输出样例#2
120
说明提示
0≤a≤9
1≤k≤100
#include <iostream>
using namespace std;
int main() {
int a, k;
cin >> a >> k;
int count = 0;
for (int page = 1; ; page++) {
int temp = page;
while (temp > 0) {
int digit = temp % 10;
if (digit == a) {
count++;
if (count == k) {
cout << page << endl;
return 0;
}
}
temp /= 10;
}
}
return 0;
}分组均衡性
在上机实验课上,老师将所有学生排列为 n 排,每排坐 m 个学生。每个学生有左右两个邻座(除了这一排的左右两端)。每个人可以和自己的邻座互相帮助完成实验。除了每排左右两端的学生,中间的每个学生都可以同时与两个邻座分别协作。
由于每个学生的个人能力不同,假设协作产生的小组能力值是两个协作学生的能力值之和,老师希望知道,自己给出的座位安排在多大程度上是“均衡”的 —— 所谓分组均衡性,是指所有可能组成的协作小组的能力值的最大值与最小值之差。
给定一张座位安排表,请计算这个安排的分组均衡性。
时间限制:1000
内存限制:65536
输入
输入第一行给出 2 个正整数 n 和 m(2 ≤ n, m ≤ 100),依次为座位的排数和每排的人数。 随后 n 行,每行给出 m 个数字,代表对应座位上学生的能力值(为区间 [1, 100] 内的整数)。同行数字间以空格分隔。
输出
在一行中输出分组均衡性。
样例输入
3 5 10 80 30 95 60 79 55 63 84 41 98 23 72 85 58
样例输出
67
提示
样例解释:最强组合是第 3 排的 72+85=157;最弱组合是第 1 排的 10+80=90。因此两者之差为 67。
//参考代码1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, a[110], b = 0, s = 1000000, bt, st, c;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[j];
}
for (int j = 1; j < m ; j++) {
c = a[j] + a[j - 1];
if (c > b) {
b = c;
}
if (c < s) {
s = c;
}
}
}
cout << b - s;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int max_sum = INT_MIN;
int min_sum = INT_MAX;
for (int i = 0; i < n; ++i) {
vector<int> row(m);
for (int j = 0; j < m; ++j) {
cin >> row[j];
}
// 计算当前行的所有相邻小组能力值
for (int j = 0; j < m - 1; ++j) {
int current_sum = row[j] + row[j + 1];
max_sum = max(max_sum, current_sum);
min_sum = min(min_sum, current_sum);
}
}
cout << max_sum - min_sum << endl;
return 0;
}狼人杀简单版
以下文字摘自《灵机一动·好玩的数学》:“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中,1 号玩家说:“2 号是狼人”,2 号玩家说:“3 号是好人”,3 号玩家说:“4 号是狼人”,4 号玩家说:“5 号是好人”,5 号玩家说:“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色,有 2 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家?
本题是这个问题的升级版:已知 n 名玩家中有 2 人扮演狼人角色,有 2 人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家?
时间限制:1000
内存限制:65536
输入
输入在第一行中给出一个正整数 n(5 ≤ n ≤ 100)。随后 n 行,第 i 行给出第 i 号玩家说的话(1 ≤ i ≤ n),即一个玩家编号,用正号表示好人,负号表示狼人。
输出
如果有解,在一行中按递增顺序输出 2 个狼人的编号,其间以空格分隔,行首尾不得有多余空格。如果解不唯一,则输出最小序列解 —— 即对于两个序列 A = { a[1], ..., a[M] } 和 B = { b[1], ..., b[M] },若存在 0 ≤ k < M 使得 a[i]=b[i] (i ≤ k),且 a[k+1] < b[k+1],则称序列 A 小于序列 B。若无解则输出 `No Solution`。
样例输入
样例#1:
5 -2 +3 -4 +5 +4
样例#2:
6 +6 +3 +1 -5 -2 +4
样例#3:
5 -2 -3 -4 -5 -1
样例输出
样例#1:
1 4
样例#2:
1 5
样例#3:
No Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> statements(n);
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
statements[i] = stoi(s);
}
// 枚举所有可能的狼人组合(x, y),其中 x < y
for (int x = 1; x <= n; ++x) {
for (int y = x + 1; y <= n; ++y) {
int lieCount = 0;
bool wolfLie = false;
bool xTruth = false, yTruth = false;
// 验证每个玩家的发言
for (int i = 0; i < n; ++i) {
int target = abs(statements[i]);
bool actual = (target == x || target == y); // 实际是否为狼人
bool claim = (statements[i] < 0); // 玩家的断言是否为狼人
// 判断是否说谎
if (actual != claim) {
lieCount++;
if (i + 1 == x || i + 1 == y) wolfLie = true; // 狼人是否说谎
}
// 记录狼人的发言真实性
if (i + 1 == x) xTruth = (actual == claim);
if (i + 1 == y) yTruth = (actual == claim);
}
// 验证条件:恰好两个谎言、有狼人说谎、狼人发言不同
if (lieCount == 2 && wolfLie && xTruth != yTruth) {
cout << x << " " << y << endl;
return 0;
}
}
}
cout << "No Solution" << endl;
return 0;
}增高垫
网传最大号的增高垫有 16 厘米,可以一下把 1.64 米的男孩变成一米八的大汉,不少对自己身高缺乏自信的男生女生会悄悄买来穿,特别是大家站成一排拍照的时候。
假设准备拍照的一排人中,只要有人看到身边紧挨着的人比自己高,就会忍不住穿增高垫,并且一定要比人家多穿一层。你的任务就是在看过这一排人的身高后,算出谁穿了最多层的增高垫。
时间限制:1000
内存限制:65536
输入
输入首先在第一行给出正整数 n(≤ 104),为一排人的个数。随后一行给出 n 个正整数,表示 n 个人的身高(厘米)。每个数值是不超过 300 的正整数,数字间以空格分隔。
输出
在一行中输出穿了最多层增高垫的人的位置和穿的层数(位序从左到右,从 1 开始)。如果有并列,按从左到右的顺序,每个人的信息占一行。
样例输入
10 150 160 186 200 170 175 180 186 186 183
样例输出
1 3 5 3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> height(n);
for (int i = 0; i < n; ++i) {
cin >> height[i];
}
vector<int> layers(n, 0);
// 从左到右处理左边比自己高的情况
for (int i = 1; i < n; ++i) {
if (height[i - 1] > height[i]) {
layers[i] = layers[i - 1] + 1;
}
}
// 从右到左处理右边比自己高的情况
for (int i = n - 2; i >= 0; --i) {
if (height[i + 1] > height[i]) {
layers[i] = max(layers[i], layers[i + 1] + 1);
}
}
// 找出最大层数
int max_layer = *max_element(layers.begin(), layers.end());
// 输出所有层数等于最大层数的位置
for (int i = 0; i < n; ++i) {
if (layers[i] == max_layer) {
cout << i + 1 << " " << max_layer << endl;
}
}
return 0;
}