GESP-C++六级 题库
小杨和整数拆分
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一个正整数n,小杨想将它拆分成若干完全平方数的和,同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为n 的完全平方数的最少数量。
输入格式
第一行包含一个正整数n,含义如题面所示。
输出格式
输出一个整数,代表总和为n 的完全平方数的最少数量。
输入样例
输出样例
18=9+9=16+1+1,其中最少需要2 个完全平方数。

对于全部数据,保证有1≤n≤105。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int dp[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
dp[i]=i;
for(int j=1;j<=sqrt(i);j++){
dp[i] =min(dp[i-j*j]+1,dp[i]);
}
}
cout<<dp[n]<<"\n";
}题目大意:给定一个正整数n,将其拆分成若干个完全平方数的和,要求拆分的数量越少越好。求最少需要多少个完全平方数才能构成n。
用DP进行求解
状态定义
设dp[i]表示构成整数i的最少完全平方数的数量。
状态转移方程
考虑如何通过已知的dp[j](其中j < i)来推导出dp[i]。
对于任意一个整数i,我们可以考虑将它拆分成一个完全平方数j2加上剩余部分i - j2 的和。因此,
dp[i]可以通过dp[i - j2] 来推导出来,即:
dp[i] =min 1≤ k ≤ i (dp[ i−j 2 ]+1)
解释:
dp[i - j2] 表示剩余部分 i - j2 的最少完全平方数数量。+ 1 表示当前添加了一个完全平方数 j2。
我们需要取所有可能的 j 的最小值,以确保 dp[i] 最小。
算法学习
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨计划学习 m 种算法,为此他找了 n 道题目来帮助自己学习,每道题目至多学习一次。
小杨对于 m 种算法的初始掌握程度均为 0 。第 i 道题目有对应的知识点ai,即学习第 i 道题目可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习目标是对 m 种算法的掌握程度均至少为 k 。
小杨认为连续学习两道相同知识点的题目是不好的,小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。
输入格式
第一行三个正整数m,n,k,代表算法种类数,题目数和目标掌握程度。
第二行n个正整数a1,a2,a3,...,an,代表每道题目的知识点。
第二行n个正整数b1,b2,b3,...,bn,代表每道题目提升的掌握程度。
输出格式
输出一个整数,代表小杨最少需要学习题目的数量,如果不存在满足条件的方案,输出 -1。
输入样例1
输出样例1
输入样例2
输出样例2
对于样例1,一种最优学习顺序为第一道题,第三道题,第四道题,第二道题。

对于全部数据,保证有1≤m,n≤105,1≤bi,k≤105,1≤ai≤m。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int f[N];
vector<int> score[N + 2], a, b;
bool cmp(int i, int j) {
return i > j;
}
int main() {
int n, m, k;
cin >> m >> n >> k;
a.resize(n), b.resize(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++) {
cin >> b[i];
score[a[i]].emplace_back(b[i]);
}
vector<int> need(m + 2);
int ans = 0, mx_meed = 0, mx_need_i = -1;
for (int i = 1; i <= m; i ++) {
sort(score[i].begin(), score[i].end(), cmp);
int sum = 0;
for (int j = 0; j < (int) score[i].size(); j ++) {
sum += score[i][j];
if (sum >= k) {
need[i] = j + 1; break ;
}
}
if (sum < k) {
puts("-1"); return 0;
}
ans += need[i];
if (need[i] > mx_meed)
mx_meed = need[i], mx_need_i = i;
}
if (mx_meed - 1 <= ans - mx_meed) {
cout << ans << endl;
return 0;
}
int last = 0;
for (int i = 1; i <= m; i ++)
if (i != mx_need_i)
last += score[i].size() - need[i];
cout << (mx_meed - 1 <= ans - mx_meed + last ? 2 * mx_meed - 1 : -1) << endl;
return 0;
}1.数据准备
读入数据,并将每道题目按知识点分类,记录每种算法通过题目提升掌握程度的列表score。
2.计算每种算法所需的题目数量
对于每种算法,我们需要计算达到目标掌握程度k所需的题目数量。为了最大化利用高分题目,我们需要按分数降序排序。
3.确定最少题目数量
我们需要找到一种安排,使得小杨学习的题目数量最少,并且避免连续学习相同知识点的题目。为此,我们找出需要题目最多的算法,并尝试调整学习顺序。
4.调整学习顺序
如果最多需要的题目数量mx_need减去1之后仍然不超过总需要的题目数量减去mx_need,那么可以通过调整顺序来满足要求;否则,输出-1。
计算得分
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨想要计算由m个小写字母组成的字符串的得分。
小杨设置了一个包含n个正整数的计分序列A=[a1,a2,...,an],如果字符串的一个子串由k(1≤k≤n) 个 abc 首尾相接组成,那么能够得到分数ak,并且字符串包含的字符不能够重复计算得分,整个字符串的得分是计分子串的总和。
例如,假设a=3,字符串 dabcabcabcabzabc 的所有可能计分方式如下:d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc,其中 d 和 abz 不计算得分,总得分为a1+a2+a1d+abc+abc+abc+abz+abc,总得分为a1+a1+a1+a1d+abcabcabc+abz+abc,总得分为a3+a1
小杨想知道对于给定的字符串,最大总得分是多少。
输入格式
第一行包含一个正整数n,代表计分序列 A 的长度。
第二行包含 n 个正整数,代表计分序列A。
第三行包含一个正整数m,代表字符串的长度。
第四行包含一个由 m 个小写字母组成的字符串。
输出格式
输出一个整数,代表给定字符串的最大总得分。
输入样例
输出样例
样例解释
最优的计分方式为 d+abc+abc+abc+abz,总得分为a1+a1+a1,共9 分。
数据范围

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[30];
string s;
int dp[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int m;
cin>>m;
cin>>s;
for(int i=1;i<=m;i++){
dp[i]=dp[i-1];
for(int j=1;j<=n;j++){
if(i-3*j+1<=0)break;
int l = i-3*j+1;
if(s.substr(l-1,3)=="abc"){
dp[i]=max(dp[i],dp[l]+a[j]);
}else break;
}
}
cout<<dp[m]<<"\n";
}20分思路,考虑到ai>=ai+1,此时将abc单独算是最多的,答案为A[1]*abc的个数。
满分思路
状态表示:DP[i]表示前i个字符组成的最大得分。
状态转移方程:
对第i个字符,有两种情况:①不作为答案的一部分。②作为abc的一部分对答案产生贡献;
对于①:DP[i]=DP[i-1] (也可以理解为将i-1的答案顺延到i),这保证了答案为DP[m]
对于②:前i个字符中,最后一个位置作为“abc”,可以考虑用连续的j个abc连接更新答案;
此时i-3*j+1 ~i的范围都为连续的j个abc,产生的代价为A[j]
DP[i]=DP[i-3*j]+A[j]
①和②构成了答案的所有解
有:DP[i]=max(DP[i-1],max(DP[i-3j]+A[j]); i-3j+1>=1
二叉树
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。
小杨想知道q次操作全部完成之后每个节点的颜色。
输入格式
第一行一个正整数n,表示二叉树的节点数量。
第二行n−1个正整数,第i(1≤i≤n−1) 个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。
第三行一个长度为n的01 串,从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
第四行一个正整数q,表示操作次数。
接下来q行每行一个正整数ai(1≤ai≤n),表示第i次操作选择的节点编号。
输出格式
输出一行一个长度为n的01 串,表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
输入样例
输出样例
样例解释
第一次操作后,节点颜色为:011010
第二次操作后,节点颜色为:000000
第三次操作后,节点颜色为:010000
数据范围

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int son[N][2];
int f[N],col[N],sum[N];
void dfs(int x,int now){
now+=sum[x];
if(now&1)col[x]^=1;
for(int i=0;i<2;i++){
if(son[x][i]!=-1)dfs(son[x][i],now);
}
}
int main(){
cin>>n;
memset(son,-1,sizeof son);
for(int i=2;i<=n;i++){
cin>>f[i];
for(int j=0;j<2;j++){
if(son[f[i]][j]==-1){
son[f[i]][j]=i;
break;
}
}
}
string s;
cin>>s;
for(int i=1;i<=n;i++){
col[i]=s[i-1]-'0';
}
int q;
cin>>q;
while(q--){
int x;
cin>>x;
sum[x]+=1;
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout<<col[i];
}
cout<<"\n";
}①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。
②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。
游戏
题面描述
你有四个正整数n,a,b,c,并准备用它们玩一个简单的小游戏。
在一轮游戏操作中,你可以选择将n减去a,或是将n减去b。游戏将会进行多轮操作,直到当n≤c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某一轮游戏操作中,一种操作序列选择将n减去a,而另一种操作序列选择将n减去b。如果a=b,也认为将n减去a与将n减去b是不同的操作。
由于答案可能很大,你只需要求出答案对1000000007取模的结果。
输入格式
一行四个正整数n,a,b,c。保证1≤a,b,c≤n。
输出格式
一行一个整数,表示不同的游戏操作序列数量对1000000007取模的结果。
样例输入1
样例输出1
样例输入2
样例输出2
样例输入3
样例输出3
数据范围
对于20的测试点,保证a=b=c=1,n≤30。
对于40的测试点,保证c=1,n≤103。
对于所有测试点,保证1≤n≤2×105。
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, a, b, c;
int f[N << 1];
int ans;
int main()
{
scanf("%d%d%d%d", &n, &a, &b, &c);
f[N + n] = 1;
for (int i = n; i > c; i--)
{
f[N + i - a] = (f[N + i - a] + f[N + i]) % mod;
f[N + i - b] = (f[N + i - b] + f[N + i]) % mod;
}
for (int i = 0; i <= N + c; i++)
ans = (ans + f[i]) % mod;
printf("%d\n", ans);
return 0;
}好斗的牛
问题描述
你有109个牛棚,从左到右一字排开。你希望把N头牛安置到牛棚里。麻烦的是,你的牛很好斗,如果他们附近有其他的牛,他们就会不安分地去挑事。其中,第i头牛的攻击范围是(ai,bi),这意味着,如果他的左边ai个牛棚或右边bi个牛棚里有其他牛,他就会去挑事。
你想留下连续的一段牛棚,并把其他牛棚都卖掉。请问你最少需要留下多少牛棚,才能保证至少存在一种方案能够把所有的N头牛都安置进剩余的牛棚里,且没有牛会挑事?
输入描述
第一行 1 个正整数N。
接下来一行N个用空格隔开的正整数a1,...,aN。
接下来一行 个用空格隔开的正整数b1,...,bN。
输出描述
输出一行一个整数,表示你最少需要留下多少牛棚。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1

你可以留下 个牛棚,并如此安排你的牛:
样例输入 2
样例输出 2
数据规模
对于20的测试点,保证N=2;
对于另外20的测试点,保证N=3;
对于80的测试点,保证N≤8;
对于所有测试点,保证N≤9,ai,bi≤1000。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
vector<int> a, b;
int ans = 1e9;
int main() {
cin >> N;
a.resize(N);
b.resize(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
for (int i = 0; i < N; ++i) {
cin >> b[i];
}
vector<int> permutation;
permutation.resize(N);
for (int i = 0; i < N; i ++)
permutation[i] = i;
do {
int curr_len = N;
for (int i = 1; i < N; ++i) {
curr_len += max(b[permutation[i - 1]], a[permutation[i]]);
}
ans = min(ans, curr_len);
} while(next_permutation(permutation.begin(), permutation.end()));
cout << ans << endl;
return 0;
}闯关游戏
时间限制:1.0 s
内存限制:128.0 MB
问题描述
你来到了一个闯关游戏。
这个游戏总共有N关,每关都有M个通道,你需要选择一个通道并通往后续关卡。其中,第i个通道可以让你前进ai关,也就是说,如果你现在在第x关,那么选择第i个通道后,你将直接来到第x+ai关(特别地,如果x+ai≥N,那么你就通关了)。此外,当你顺利离开第s关时,你还将获得bs分。
游戏开始时,你在第0关。请问,你通关时最多能获得多少总分?
输入描述
第一行两个整数N,M,分别表示关卡数量和每关的通道数量。
接下来一行M个用单个空格隔开的整数a0,a1,……,aM-1。保证1≤ai≤N。
接下来一行N个用单个空格隔开的整数b0,b1,……,bN-1。保证|bi|≤105。
输出描述
一行一个整数,表示你通关时最多能够获得的分数。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
你可以在第0关选择第1个通道,获得1分并来到第3关;随后再选择第0个通道,获得100分并来到第5关;最后任选一个通道,都可以获得30分并通关。如此,总得分为1+100+30=131。
样例输入 2
样例输出 2
样例解释 2
请注意,一些关卡的得分可能是负数。
数据规模
对于20%的测试点,保证M=1。
对于40%的测试点,保证N≤20;保证M≤2。
对于所有测试点,保证N≤104;保证M≤100。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int N = 10005;
const int M = 105;
const int inf = 0x3f3f3f3f;
int a[M], b[N], f[N];
int main() {
// freopen("data/1.in", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
scanf("%d", &b[i]);
memset(f, -0x3f, sizeof(f));
f[0] = 0;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
if (i - a[j] >= 0)
f[i] = max(f[i], f[i - a[j]] + b[i - a[j]]);
int ans = -inf;
for (int i = 0; i < n; i++)
for (int j = 1; j <= m; j++)
if (i + a[j] >= n) {
ans = max(ans, f[i] + b[i]);
break;
}
cout << ans << endl;
return 0;
}工作沟通
时间限制:1.0 s
内存限制:128.0 MB
问题描述
某公司有N名员工,编号从0至N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度,每位员工只能受到本人或本人直接领导或间接领导的管理。具体来说,规定员工x可以管理员工y,当且仅当x=y,或f=fy,或x可以管理fy。特别地,0号员工老板只能自我管理,无法由其他任何员工管理。
现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?
输入描述
第一行一个整数N,表示员工的数量。
第二行N-1个用空格隔开的正整数,依次为f1,f2…,fN-1。
第三行一个整数Q,表示共有Q场合作需要安排。
接下来Q行,每行描述一场合作:开头是一个整数m(2≤m≤N),表示参与本次合作的员工数量;接着是m个整数,依次表示参与本次合作的员工编号(保证编号合法且不重复)。
保证公司结构合法,即不存在任意一名员工,其本人是自己的直接或间接领导。
输出描述
输出Q行,每行一个整数,依次为每场合作的主持人选。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
对于第一场合作,员工3,4有共同领导2,可以主持合作。
对于第二场合作,员工2本人即可以管理所有参与者。
对于第三场合作,只有0号老板才能管理所有员工。
样例输入 2
样例输出 2
数据规模
对于50%的测试点,保证N≤50。
对于所有测试点,保证3≤N≤300;Q≤100 。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
const int N = 305;
int fa[N], dep[N];
bool vis[N];
vector<int> ch[N];
int getdep(int x) { return x == 0 ? 0 : getdep(fa[x]) + 1; }
void dfs(int x) {
vis[x] = 1;
for (int y : ch[x])
dfs(y);
}
bool check(int x, int n, const vector<int> &vec) {
for (int i = 0; i <= n; i++)
vis[i] = 0;
dfs(x);
for (int y : vec)
if (!vis[y])
return 0;
return 1;
}
int main() {
// freopen("data/1.in", "r", stdin);
// freopen("tmp.txt", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d", &fa[i]);
ch[fa[i]].push_back(i);
}
for (int i = 1; i < n; i++)
dep[i] = getdep(i);
int q;
scanf("%d", &q);
while (q--) {
int m, mnd = n + 1;
scanf("%d", &m);
vector<int> vec(m);
for (int i = 0; i < m; i++) {
scanf("%d", &vec[i]);
mnd = min(mnd, dep[vec[i]]);
}
for (int i = n - 1; i >= 0; i--)
if (dep[i] <= mnd && check(i, n, vec)) {
printf("%d\n", i);
break;
}
}
return 0;
}小杨买饮料(2023.9C++六级)
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小杨来到了一家商店,打算购买一些饮料。这家商店总共出售N种饮料,编号从0至N-1,其中编号为i的饮料售价ci元,容量li毫升。
小杨的需求有如下几点:
1. 小杨想要尽可能尝试不同种类的饮料,因此他希望每种饮料至多购买 1 瓶;
2. 小杨很渴,所以他想要购买总容量不低于L的饮料;
3. 小杨勤俭节约,所以在 1 和 2 的前提下,他希望使用尽可能少的费用。
方便起见,你只需要输出最少花费的费用即可。特别地,如果不能满足小杨的要求,则输出 no solution 。
输入描述
第一行两个整数N,L。
接下来N行,依次描述第i=0,1,...,N-1种饮料:每行两个整数ci,li。
输出描述
输出一行一个整数,表示最少需要花费多少钱,才能满足小杨的要求。特别地,如果不能满足要求,则输出 no
solution 。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
5 100
100 2000
2 50
4 40
5 30
3 20
样例输出 1
9
样例解释 1
小杨可以购买1,2,4号饮料,总计获得50+40+20=110毫升饮料,花费2+4+3=9元。
如果只考虑前两项需求,小杨也可以购买1,2,4号饮料,它们的容量总和为50+30+20=100毫升,恰好可以满足需求。但遗憾的是,这个方案需要花费2+5+3=10元。
样例输入 2
5 141
100 2000
2 50
4 40
5 30
3 20
样例输出 2
100
样例解释 2
1,2,3,4号饮料总计140毫升,如每种饮料至多购买 1 瓶,则恰好无法满足需求,因此只能花费100元购买0号饮料。
样例输入 3
4 141
2 50
4 40
5 30
3 20
样例输出 3
no solution
数据规模
对于40%的测试点,保证N≤20 ;1≤L≤100 ;li≤100。
对于70%的测试点,保证li≤100。
对于所有测试点,保证1≤N≤500 ;1≤L≤2000 ;1≤ci,li≤106。
#include <iostream>
using namespace std;
const int INF = 1000000000;
int cost[2001];
int main() {
int N = 0, L = 0;
cin >> N >> L;
cost[0] = 0;
for (int i = 1; i <= L; i++)
cost[i] = INF;
for (int i = 0; i < N; i++) {
int c = 0, l = 0;
cin >> c >> l;
for (int j = L; j >= 0; j--)
cost[j] = min(cost[j], cost[max(j - l, 0)] + c);
}
if (cost[L] == INF)
cout << "no solution" << endl;
else
cout << cost[L] << endl;
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;
}