- 1python 分词 词性_使用NLTK进行分词及词性标注
- 2RPA走专有云还是公共云？阿里云RPA公共云给出了这样几组数据…_电商rpa site:blog.csdn.net
- 3关于ONgDB我问了ChatGPT这些问题！_ongdb neo4j区别
- 4哈理工计算机考研调剂,2020哈尔滨理工大学考研调剂信息(二)
- 5Docker 发布首个支持 WebAssembly 预览版
- 6ChatGPT：如何安装使用插件？超详细的教程！_chatgpt安装
- 7IAF R-CNN：针对多光谱行人目标检测的光照感知Faster R-CNN_多光谱目标检测
- 8python中异常值的检测和处理_python实现异常检验算法的代码
- 9蜣螂优化算法---蜣螂（粪甲虫）优化器（DBO）理论与MATLAB代码实现_dbo优化mlp代码 matlab
- 10如何训练你的准确率？
[第五届蓝桥杯省赛C++B组]省赛全题目题解_第五届蓝桥杯b组c++
赞
踩
文章目录
快速分支通道
酒精与饮料
切面条
李白打酒
史丰收运算
打印图形
奇怪的分式
六角填数
蚂蚁感冒
地宫取宝
小朋友排队
1.题目 啤酒和饮料
算法标签： 枚举
题目描述：
啤酒每罐2.3元，饮料每罐1.9元。小明买了若干啤酒和饮料，一共花了82.3元。
我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。
注意：答案是一个整数。请通过浏览器提交答案。
不要书写任何多余的内容（例如：写了饮料的数量，添加说明文字等）。
题目答案：
11
题目思路：
数据小，题目意思明显，暴力枚举，需要注意的就是浮点计算精度用==出错。
题目代码：
#include<iostream>
using namespace std;
int main()
{
for(int i=1;i<=82.3/1.9;i++)//i啤酒 j饮料
for(int j=0;j<i;j++)
if(i*19+j*23==823)cout<<j;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
2.题目 切面条
来源：第五届蓝桥杯省赛C++B组
算法标签 递推
题目描述：
一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。
那么，连续对折10次，中间切一刀，会得到多少面条呢？
答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。
题目答案：
1025
题目思路：
观察表述，所有x有对应y.
x y
0 2
1 3
2 5
不难理解，所有当前状态下的面条都更新为上一个的(N-1)*2+切割状态中不变的一个。
在这个过程中，未对折的f0不受影响。
则我们发现，所有当前状态都受到上一个状态决定，是递推,得到(f[i-1]-1)*2+1，拆开即为f[i]=f[i-1]*2-1;
题目代码：
#include<iostream>
using namespace std;
int main()
{
int f[10];
f[1]=3;
for(int i=2;i<11;i++)f[i]=f[i-1]*2-1;//等同(f[i-1]-1)*2+1
cout<<f[10];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
3.题目 李白打酒
算法标签：dfs
题目描述：
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
题目答案：
14
题目思路：
变量单位有：花 、店、酒
且我们得到信息逢店加一倍，遇花喝一斗。这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
则表明如果遇到店，酒*2，如果遇到花，酒-1，当到了第15次选择完毕之后退出。
由此我们可以利用暴搜抓出每一个状态找出符合条件的次数。
题目代码：
dfs
#include<iostream> using namespace std; int cnt; void dfs(int a,int b,int sum,int u,int flag)//分别表示 店 花 酒量 位置 最后一个位置表示 { if(u==15) { if(a==5&&b==10&&sum==0&&flag==0) { cnt++; return; } } else { dfs(a+1,b,sum*2,u+1,1);//下一个遇到店 dfs(a,b+1,sum-1,u+1,0);//下一个遇到花 } } int main() { dfs(0,0,2,0,0); cout<<cnt; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
二进制
int ans = 0; for (int i = 0; i < (1<<14); ++i) { int tot_1 = 0; int tot_0 = 0; int num = 2; for (int j = 0; j < 14; ++j) { if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1 tot_1++; num = num * 2; } else { tot_0++; num = num - 1; } } if (tot_1 == 5 && tot_0 == 9 && num == 1) { ++ans; // 记录合法方案数 } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
4.题目 史丰收运算
算法标签：
题目描述：
史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!
速算的核心基础是：1位数乘以多位数的乘法。
其中，乘以7是最复杂的，就以它为例。
因为，1/7 是个循环小数：0.142857…，如果多位数超过 142857…，就要进1
同理，2/7, 3/7, … 6/7 也都是类似的循环小数，多位数超过 n/7，就要进n
下面的程序模拟了史丰收速算法中乘以7的运算过程。
乘以 7 的个位规律是：偶数乘以2，奇数乘以2再加5，都只取个位。
乘以 7 的进位规律是：
满 142857… 进1,
满 285714… 进2,
满 428571… 进3,
满 571428… 进4,
满 714285… 进5,
满 857142… 进6
请分析程序流程，填写划线部分缺少的代码。
思路
有题目得到信息
因为，1/7 是个循环小数：0.142857…，如果多位数超过 142857…，就要进1 同理，2/7, 3/7, … 6/7
也都是类似的循环小数，多位数超过 n/7，就要进n
我们观察jin_wei部分的代码，发现如果level与buf相同则要进行持续的比较，且题目中出现buf比level[i]大的状态产生进位进到第n位。
则我们可以很明显的发现代码中缺乏buf比level[i]小的状态下的判断，此时不足level[i],不进位，返回当前状态，则为if(r>0)return i;
题目代码
//计算个位 int ge_wei(int a) { if(a % 2 == 0) return (a * 2) % 10; else return (a * 2 + 5) % 10; } //计算进位 int jin_wei(char* p) { char* level[] = { "142857", "285714", "428571", "571428", "714285", "857142" }; char buf[7]; buf[6] = '\0'; strncpy(buf,p,6); int i; for(i=5; i>=0; i--){ int r = strcmp(level[i], buf); if(r<0) return i+1; while(r==0){ p += 6; strncpy(buf,p,6); r = strcmp(level[i], buf); if(r<0) return i+1; //______________________________; //填空 } } return 0; } //多位数乘以7 void f(char* s) { int head = jin_wei(s); if(head > 0) printf("%d", head); char* p = s; while(*p){ int a = (*p-'0'); int x = (ge_wei(a) + jin_wei(p+1)) % 10; printf("%d",x); p++; } printf("\n"); } int main() { f("428571428571"); f("34553834937543"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
题目答案
if(r)return i;
- 1
5.题目 打印图形
算法标签：
题目描述：
小明在X星球的城堡中发现了如下图形和文字：
- 1
rank=3
*
* *
* *
* * * *
rank=5
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
ran=6
```cpp
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
```
思路
题目代码
小明开动脑筋，编写了如下的程序，实现该图形的打印。
#define N 70 void f(char a[][N], int rank, int row, int col) { if(rank==1){ a[row][col] = '*'; return; } int w = 1; int i; for(i=0; i<rank-1; i++) w *= 2; ____________________________________________; f(a, rank-1, row+w/2, col); f(a, rank-1, row+w/2, col+w); } int main() { char a[N][N]; int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) a[i][j] = ' '; f(a,6,0,0); for(i=0; i<N; i++){ for(j=0; j<N; j++) printf("%c",a[i][j]); printf("\n"); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
请仔细分析程序逻辑，填写缺失代码部分。
通过浏览器提交答案。注意不要填写题目中已有的代码。也不要写任何多余内容（比如说明性的文字）
题目思路：
我们可以观察发现，i=4时，图形是i=3时的三倍组成的三角形，推到i=6逻辑成立。
则我们可以明确，在图形的构造上面而言f[i]=f[i-1]*3;
此时我们一rank==6来观察。
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
____________________________________________;
f(a, rank-1, row+w/2, col);
f(a, rank-1, row+w/2, col+w);
- 1
- 2
- 3
变量名称中row的意思为行，col的意思为列。
同时我们发现下两行递归调用自身，且依据刚才推论出的原则，我们不难联想出可能出这些式子都是用来递归构造三个三角型，又因为坐标不同其实是为了构建不同位置的三角形。
则很明显的是，下两行行数相同，列不同，表明最下面的两个三角形的构造，则我们需要补充的实际是顶端三角形的构造。
但实际上我们的问题转化为了，顶端三角形递归构造的坐标。
则很明显我们的顶部三角形必然为f(a, rank-1, row, ？);
我们只需要查找？所代表的偏移量等于多少即可。
直接查看第一个三角形图像查找起始位置即可。
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
则答案等于f(a, rank-1, row, col+w/2);
题目答案：
f(a, rank-1, row, col+w/2);
- 1
6.题目 奇怪的分式
来源：第五届蓝桥杯省赛C++B组
算法标签：dfs，枚举,gcd
题目描述：
上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：
1/4 乘以 8/5
小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见图1.png）
老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！
对于分子、分母都是 1~9 中的一位数的情况，还有哪些算式可以这样计算呢？
请写出所有不同算式的个数（包括题中举例的）。
显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。
但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列!
注意：答案是个整数（考虑对称性，肯定是偶数）。请通过浏览器提交。不要书写多余的内容。
题目答案：
14
题目思路：
1.DFS 按题目要求来说我们很直接的就想到了暴搜+判断，但这其中我们要注意将(a/b)(c/d)转换为(ac)/(bd),以及分数问题转换为double判断。
2.GCD 另一个方向则是直接枚举，将 (a/b)(c/d)转换为(ac)/(bd)，不通过整体， 而是利用gcd求出最大公约数，再分子分母分别比较，如果都相同则是答案，例如1 6 4 3,做a b处理变为：4/18,14/63,gcd（a约2，b约9）之后变为2/9，2/9,相同+1；
题目代码：
gcd
#include<iostream> using namespace std; int gcd(int a,int b){return b?gcd(b,a%b):a;} int main(){ int ans = 0; for(int a=1;a<10;a++) for(int b=1;b<10;b++) for(int c=1;c<10;c++) for(int d=1;d<10;d++) if(a!=b&&c!=d) { int g1=gcd(a*c,b*d),g2=gcd(a*10+c,b*10+d); if(a*c/g1==(a*10+c)/g2 && b*d/g1==(b*10+d)/g2)ans++; } cout<<ans; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
dfs
#include<iostream> using namespace std; int ans; double num[4]; bool check(){return num[0]!=num[1]&&num[2]!=num[3];} void dfs(int u) { if(u>4)return ; if(u==4) { if(check()) { double a=(num[0]*num[2])/(num[1]*num[3]); double b=(num[0]*10.0+num[2])/(num[1]*10.0+num[3]); if(a==b)ans++; } return; } else { for(int i=1;i<=9;i++) { num[u]=i; dfs(u+1); num[u]=0; } } } int main() { dfs(0); cout<<ans; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
7.题目 六角填数
算法标签：全排列
题目描述：
如图【1.png】所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。
题目答案：
10
题目思路：
根据题意我们只需要填满每个空位然后全排列判断即可。
需要注意的是1、2、12位已经被固定。
题目代码：
#include<iostream> #include<algorithm> using namespace std; int n[12]={1,2,3,4,5,6,7,8,9,10,11,12}; int main() { do{ int line1=n[0]+n[2]+n[5]+n[7]; int line2=n[0]+n[3]+n[6]+n[10]; int line3=n[7]+n[8]+n[9]+n[10]; int line4=n[1]+n[2]+n[3]+n[4]; int line5=n[1]+n[5]+n[8]+n[11]; int line6=n[4]+n[6]+n[9]+n[11]; if(line1==line2&&line2==line3&&line3==line4&&line4==line5&&line5==line6 &&n[0]==1&&n[1]==8&&n[11]==3)cout<<n[5]; }while(next_permutation(n,n+12)); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
8.题目 蚂蚁感冒
算法标签：数学
题目描述
长 100 厘米的细长直杆子上有 n 只蚂蚁。
它们的头有的朝左，有的朝右。
每只蚂蚁都只能沿着杆子向前爬，速度是 1 厘米/秒。
当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。
这些蚂蚁中，有 1 只蚂蚁感冒了。
并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。
请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
输入格式
第一行输入一个整数 n, 表示蚂蚁的总数。
接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。
正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。
其中，第一个数据代表的蚂蚁感冒了。
输出格式
输出1个整数，表示最后感冒蚂蚁的数目。
数据范围
1<n<50,
0<|Xi|<100
- 1
- 2
输入样例1：
3
5 -2 8
- 1
- 2
输出样例1：
1
- 1
输入样例2：
5
-10 8 -20 12 25
- 1
- 2
输出样例2：
3
- 1
思路
依据下图分析：
1.有蚂蚁N个，母体一个，最重要的关系就是速度恒等，也就是方向相同，后者追不上前者。
2.将双方撞上，题目中的逻辑是掉头返回，但也可以视作做无体积碰撞前进，
3.在母体右边且往左走的蚂蚁与在母体左边且往右走的蚂蚁必定被感染
为什么这么想？（无体积碰撞前进）
因为在速度恒等，与母体为坐标中心的设定下，排除母体的两端蚂蚁相撞之后，与原有路线数量完全一致。
C++ 代码
#include<iostream> using namespace std; const int N=1e5+10; int l,r,a[N]; int main() { int n; cin>>n; for(int i=0;i<=n;i++) { cin>>a[i]; if(i)//0作为基准，1再判断，能省一点是一点 if(a[i]>0&&abs(a[i])<abs(a[0]))l++;//当前蚂蚁向左走，蚂蚁自身在母体蚂蚁右边，必然被感染 else if(a[i]<0&&abs(a[i])>abs(a[0]))r++;//蚂蚁向右走 蚂蚁自身在母体蚂蚁左边，必然被感染 } if(a[0]<0&&!l||a[0]>0&&!r)cout<<1;//如果所有蚂蚁都保持一个方向，就输出母体一个 else cout<<l+r+1; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
9.题目 地宫取宝
算法标签：动态规划,DP
题目描述：
X 国王有一个地宫宝库，是 n×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。
输入格式
第一行 3 个整数，n,m,k，含义见题目描述。
接下来 n 行，每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数，表示正好取 k 个宝贝的行动方案数。
该数字可能很大，输出它对 1000000007 取模的结果。
数据范围
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
输入样例1：
2 2 2
1 2
2 1
输出样例1：
2
输入样例2：
2 3 2
1 2 3
2 1 5
输出样例2：
14
思路
注意
1. 2.1E9爆栈 val = (val + f[i-1][j][u][v])%MOD; 加两个数可以，可能加三个数就爆炸了
2. 因为价值C的数据是从0到12，而我们一开始不选择的时候**f[i][j][u][v]**,此时v存在不选择的情况 则我们可以填写**比0小的数字-1**; 但因为-1无法做数组下标，因为我们直接对所有价值全部加1，就变成了1到13，原有的0就可以作为不选择的下标了。
思路图
题目代码
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int MOD=1000000007 ,N=55; int map[N][N];//地图的值 int dp[N][N][13][14];//DP[A][B][C][D] AB横纵坐标 C数量 D最后一个为D的价值 int main() { int n,m,k;//n m横纵数量 k K件宝物 cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>map[i][j]; map[i][j]++; }//读入地图宝物价值，为了方便初始下标判断，全加1 dp[1][1][1][map[1][1]]=1;//起始点选择 方案数1 dp[1][1][0][0]=1;//起始点不选 方案数1 for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i==1&&j==1)continue;//如果是起始点 跳过 for(int u=0;u<13;u++) for(int v=0;v<14;v++) { int &val = dp[i][j][u][v];//引用 简化 val = (val+dp[i-1][j][u][v])%MOD;//左边 不选 val = (val+dp[i][j-1][u][v])%MOD;//上边 不选 if(u>0&&v==map[i][j])//最终的选择到了最大的价值宝物（因为题目递增），且有选择次数，则累加不同价值的子集 { for(int c=0;c<v;c++)// { val = (val+dp[i-1][j][u-1][c])%MOD;//左边 val = (val+dp[i][j-1][u-1][c])%MOD;//上边 } } } } } int res=0; for(int i=1;i<=13;i++)res= (res+dp[n][m][k][i])%MOD;//总方案数量等于当前数量下所有价值的数量总和 cout<<res; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
10.题目 小朋友排队
小朋友排队
算法标签 树状数组 贪心 并归排序
题目描述
n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
输入的第一行包含一个整数 n，表示小朋友的个数。
第二行包含 n 个整数 H1,H2,…,Hn，分别表示每个小朋友的身高。
输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
数据范围
1≤n≤100000,
0≤Hi≤1000000
- 1
- 2
输入样例：
3
3 2 1
- 1
- 2
输出样例：
9
- 1
样例解释
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
思路
直接考虑n^2，数据过大，但我们只需要了解 不满是固定的 一个数字的交换次数=比这个数大的数字的个数+比这个数字小的数字的个数
又因为 当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k拿公式n*(n-1)/2得出
然后需要将所有的小朋友的不满值累加即可
C++ 代码
#include<iostream> #include<cstring> using namespace std; typedef long long LL; const int N=1e6+10; int h[N],s[N],tr[N];//h高，s多少个大于h[i]和小于h[i]的人,tr树状数组 int n; int lowbit(int x){return x&-x;} int add(int x){for(int i=x;i<N;i+=lowbit(i))tr[i]++;}//这里不是添加值，支持计算次数，所以自增1 int q(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res+=tr[i]; return res; } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>h[i],h[i]++;//树状数组必须从1开始 s[i]=q(N-1)-q(h[i]);//比i大的数 add(h[i]); } memset(tr,0,sizeof tr);//tr清零重复使用 for(int i=n-1;i>=0;i--)s[i]+=q(h[i]-1),add(h[i]);//逆序比较//比h[i]小的数 LL res=0; for(int i=0;i<n;i++)res+=(LL)s[i]*(s[i]+1)/2;//公式计算 累加 因为过大所以用LL cout<<res; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
