charmmm

用户名：1420462013

访问量：3852

签　名：

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

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

递增三元组（C代码）

　　作者: charmmm　　　　发表时间：2022-03-10 20:19:51 浏览：718　|　评论：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语言程序设计教程（第三版）课后习题7.3 （C语言代码）

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

点我有惊喜！你懂得！

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

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

递增三元组（C代码）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

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

1024题解

Hello, world! （C语言代码）

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

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

C语言训练-排序问题<1> （C语言代码）

【计算球体积】（C语言代码）

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

1202题解

charmmm

TA的其他文章

你可能喜欢

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

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

点我有惊喜！你懂得！

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

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

递增三元组（C代码）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

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

1024题解

Hello, world! （C语言代码）

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

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

C语言训练-排序问题<1> （C语言代码）

【计算球体积】 （C语言代码）

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

1202题解

　　评论区

【计算球体积】（C语言代码）