当前位置: 首页 > article >正文

gesp(C++六级)(4)洛谷:B3874:[GESP202309 六级] 小杨的握手问题

gesp(C++六级)(4)洛谷:B3874:[GESP202309 六级] 小杨的握手问题

在这里插入图片描述

题目描述

小杨的班级里共有 N N N 名同学,学号从 0 0 0 N − 1 N-1 N1

某节课上,老师安排全班同学进行一次握手游戏,具体规则如下:老师安排了一个顺序,让全班 N N N 名同学依次进入教室。每位同学进入教室时,需要和 已经在教室内学号小于自己 的同学握手。

现在,小杨想知道,整个班级总共会进行多少次握手。

提示:可以考虑使用归并排序进行降序排序,并在此过程中求解。

输入格式

输入包含 2 2 2 行。第一行一个整数 N N N ,表示同学的个数;第二行 N N N 个用单个空格隔开的整数,依次描述同学们进入教室的顺序,每个整数在 0 ∼ N − 1 0 \sim N-1 0N1 之间,表示该同学的学号。

保证每位同学会且只会进入教室一次。

输出格式

输出一行一个整数,表示全班握手的总次数。

样例 #1

样例输入 #1

4
2 1 3 0

样例输出 #1

2

样例 #2

样例输入 #2

6
0 1 2 3 4 5

样例输出 #2

15

提示

样例解释 1:

2 2 2 号同学进入教室,此时教室里没有其他同学。

1 1 1 号同学进入教室,此时教室里有 2 2 2 号同学。 1 1 1 号同学的学号小于 2 2 2 号同学,因此他们之间不需要握手。

3 3 3 号同学进入教室,此时教室里有 1 , 2 1,2 1,2 号同学。 3 3 3 号同学的学号比他们都大,因此 3 3 3 号同学需要分别和另外两位同学握手。

0 0 0 号同学进入教室,此时教室里有 1 , 2 , 3 1,2,3 1,2,3 号同学。 0 0 0 号同学的学号比他们都小,因此 0 0 0 号同学不需要与其他同学握手。

样例解释2:

全班所有同学之间都会进行握手,因为每位同学来到教室时,都会发现他的学号是当前教室里最大的,所以他需要和教室里的每位其他同学进行握手。

对于 30 % 30\% 30% 的测试点,保证 N ≤ 100 N\le100 N100

对于所有测试点,保证 2 ≤ N ≤ 3 × 1 0 5 2\le N\le3\times10^5 2N3×105

AC代码(100分)

#include<bits/stdc++.h>
using namespace std;
/*思路: 
	归并排序:间复杂度为nlogn,100分 
*/
const int N=3e5+10;
int n,a[N],b[N];
long long cnt=0;
//归并排序函数
void merge(int l,int r){
	if(l==r) return;//递归边界 
	//分解 
	int mid=(l+r)/2;
	merge(l,mid);//左区间 
	merge(mid+1,r);//右区间 
	//合并
	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r){
		if(a[i]<a[j]){ 
			cnt+=(mid-i+1);//更新答案 
			b[k++]=a[j++];
		}else{
			b[k++]=a[i++];
			
		}
	} 
	while(i<=mid){
		b[k++]=a[i++];
	}
	while(j<=r){
		b[k++]=a[j++];
	}
	for(int i=l;i<=r;i++){
		a[i]=b[i];
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	merge(1,n);//归并排序 
	cout<<cnt;
	return 0;
}

文末彩蛋:

点击王老师青少年编程主页有更多精彩内容


http://www.kler.cn/a/524179.html

相关文章:

  • NoSQL与SQL比较
  • 【深度学习】 UNet详解
  • 关于WPF中ComboBox文本查询功能
  • 图神经网络驱动的节点分类:从理论到实践
  • 【物联网】ARM核常用指令(详解):数据传送、计算、位运算、比较、跳转、内存访问、CPSR/SPSR、流水线及伪指令
  • 基于物联网的火灾报警器设计与实现(论文+源码)
  • 深度学习 Pytorch 深层神经网络
  • 虚幻浏览器插件 UE与JS通信
  • 《活出人生的厚度》
  • 【Docker】快速部署 Nacos 注册中心
  • AlertDialog组件的功能与用法
  • 电信骨干网络
  • 世上本没有路,只有“场”et“Bravo”
  • kaggle比赛入门 - House Prices - Advanced Regression Techniques(第四部分)
  • c++ 定点 new
  • WGCLOUD使用详解 - 如何监控文件防篡改
  • 计算机的错误计算(二百二十四)
  • 【玩转全栈】----靓号管理系统实现
  • Qt5.14.2如何设置编译链
  • matlab中,fill命令用法
  • 简单的SQL语句的快速复习
  • 【Validator】universal-translator,实现动态多语言切换,go案例根据Accept-Language 动态设置 locale
  • 论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(六)(完结)
  • 基于SpringBoot的中老年人文化活动管理系统
  • 图论——单源最短路的扩展应用
  • 【漫话机器学习系列】064.梯度下降小口诀(Gradient Descent rule of thume)