GESP-C++六级 题库
小杨想写一个程序来算出正整数N有多少个因数,经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。( )(2023年12月C++六级)
同样的整数序列分别保存在单链表和双向链中,这两种链表上的简单冒泡排序的复杂度相同。( )(2023年12月C++六级)
5G网络中,5G中的G表示Gigabytes/s,其中 1 GB = 1024 MB。(2023.9C++六级)
有些算法或数据结构在C/C++语言中使用指针实现,一个典型的例子就是链表。因此,链表这一数据结构在C/C++语言中只能使用指针来实现。
道具商店
题目描述
道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升ai点攻击力,需要 ci 枚金币才能购买,每件道具只能购买一次。现在你有 k 枚金币,请问你最多可以提升多少点攻击力?
输入格式
第一行,两个正整数 n k ,表示道具数量以及你所拥有的金币数量。 接下来 n 行,每行两个正整数ai , ci ,表示道具所提升的攻击力点数,以及购买所需的金币数量。
输出格式
输出一行,一个整数,表示最多可以提升的攻击力点数。
样例
输入样例1
3 11 99 1 33 2 11 3
输出样例1
132
输入样例2
4 100 10 1 20 11 100 99 40 33
输出样例2
110
数据范围
对于部分测试点,保证 1 ≤k ≤500, 1 ≤ ci ≤500
对于所有测试点,保证 1 ≤n ≤500 , 1 ≤k ≤10^9 , 1 ≤ ai ≤500 , 1 ≤ ci ≤10^9
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 505;
const int oo = 1e9 + 10;
int n, k;
int f[N * N];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < N * N; i++)
f[i] = oo;
f[0] = 0;
int s = 0;
for (int i = 1; i <= n; i++) {
int a, c;
scanf("%d%d", &a, &c);
s += a;
for (int j = s; j >= a; j--)
f[j] = min(f[j], f[j - a] + c);
}
int ans = 0;
for (int i = 0; i < N * N; i++)
if (f[i] <= k)
ans = i;
printf("%d\n", ans);
return 0;
}小杨的握手问题(2023.9C++六级)
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小杨的班级里共有N名同学,学号从0至N-1。
某节课上,老师安排全班同学进行一次握手游戏,具体规则如下:老师安排了一个顺序,让全班N名同学依次进入教室。每位同学进入教室时,需要和已经在教室内且学号小于自己的同学握手。
现在,小杨想知道,整个班级总共会进行多少次握手。
提示:可以考虑使用归并排序进行降序排序,并在此过程中求解。
输入描述
输入包含2行。第一行一个整数N,表示同学的个数;第二行N个用单个空格隔开的整数,依次描述同学们进入教室的顺序,每个整数在0~N-1之间,表示该同学的学号。
保证每位同学会且只会进入教室一次。
输出描述
输出一行一个整数,表示全班握手的总次数。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
4
2 1 3 0
样例输出 1
2
样例解释 1
2号同学进入教室,此时教室里没有其他同学。
1号同学进入教室,此时教室里有2号同学。1号同学的学号小于2号同学,因此他们之间不需要握手。
3号同学进入教室,此时教室里有1,2号同学。3号同学的学号比他们都大,因此3号同学需要分别和另外两位同学握手。
0号同学进入教室,此时教室里有1,2,3号同学。0号同学的学号比他们都小,因此0号同学不需要与其他同学握手。
综上所述全班一共握手0+0+2+0=2次。
样例输入 2
6
0 1 2 3 4 5
样例输出 2
15
样例解释 2
全班所有同学之间都会进行握手,因为每位同学来到教室时,都会发现他的学号是当前教室里最大的,所以他需要和教室里的每位其他同学进行握手。
数据规模
对于30%的测试点,保证N≤100。
对于所有测试点,保证2≤N≤3×105。
#include <iostream>
using namespace std;
int num[300000];
int tmp[300000];
long long merge(int l, int r) {
if (l + 1 == r)
return 0;
int m = (l + r) / 2;
long long res = merge(l, m) + merge(m, r);
for (int i = l, j = m, k = l; k < r; k++) {
if (j == r || (i < m && num[i] > num[j])) {
tmp[k] = num[i];
i++;
} else {
tmp[k] = num[j];
j++;
res += m - i;
}
}
for (int k = l; k < r; k++)
num[k] = tmp[k];
return res;
}
int main() {
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
cin >> num[i];
cout << merge(0, n) << endl;
return 0;
}