charmmm

用户名：1420462013

访问量：3390

签　名：

少年心怀乌托邦，心仍向阳肆生长

等　　级
排　　名	722
经　　验	3741
参赛次数	1
文章发表	10
年　　龄	0
在职情况	学生
学　　校	Bilibili
专　　业

　　自我简介：

TA的其他文章

移动距离（C代码）
浏览：168

利用杨辉三角形来求组合数（C代码）
浏览：441

蓝桥杯2017年第八届真题-k倍区间
浏览：156

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

递增三元组（C代码）

　　作者: charmmm　　　　发表时间：2022-03-10 20:19:51 浏览：652　|　评论：1　

原题链接：蓝桥杯2018年第九届真题-递增三元组

看到这道题第一想法肯定是暴力解决，居然暴力也能AC，然后我提交到蓝桥杯官网发现果然没有这么简单，直接运行超时。。。
解题思路：题面上有数字大小的条件（Ai < Bj < Ck），就要联想到排序了；首先对三个大小为n的数组进行排序；从b数组的第一个元素开始，依次遍历a数组，统计小于b[1]的元素个数（cnt1）；遍历c数组，统计小于等于b[1]的元素个数(cnt2)；得b[1]处的递增三元组个数即cnt1 * (n-cnt2);然后继续遍历b数组类似上述步骤。
另外在注意一下数据规模即可
代码如下：
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXN 100000
typedef long long LL;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int compare(const void *p1,const void *p2){
	return (*(int *)p1-*(int *)p2);
}
int cnt1=0;//统计a数组中小于b[i]的元素数目
int cnt2=0;//统计b数组中小于等于b[i]的元素数目
int main(){
	int n,i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(i=1;i<=n;i++)	scanf("%d",&b[i]);
	for(i=1;i<=n;i++)	scanf("%d",&c[i]);
	//对三元组进行排序
	qsort(a+1,n,sizeof(int),compare);
	qsort(b+1,n,sizeof(int),compare);
	qsort(c+1,n,sizeof(int),compare);
	LL sum=0;
	int begain1=1;
	int begain2=1;
	for(i=1;i<=n;i++){//遍历b数组 
		for(j=begain1;j<=n;j++){
			if(a[j]<b[i]){
				cnt1++;
			}else break;
		}
		for(k=begain2;k<=n;k++){
			if(c[k]<=b[i]){
				cnt2++;
			}else break;
		}
		sum+=((LL)cnt1*(n-cnt2));
		begain1=cnt1+1;
		begain2=cnt2+1;
	}
	printf("%lld",sum);
	return 0;
}
```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

lizuwangCode

还不错

2024-03-05 14:30:45

charmmm

TA的其他文章

你可能喜欢

输出九九乘法表（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

递增三元组（C代码）

评论区

精彩推荐

哥德巴赫曾猜测（C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

文科生的悲哀（C语言代码）

sizeof的大作用（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

charmmm

TA的其他文章

你可能喜欢

输出九九乘法表 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

递增三元组（C代码）

评论区

精彩推荐

哥德巴赫曾猜测 （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

文科生的悲哀 （C语言代码）

sizeof的大作用 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

输出九九乘法表（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

【计算直线的交点数】（C语言代码）

文科生的悲哀（C语言代码）

sizeof的大作用（C语言代码）

Tom数（C语言代码）