charmmm

用户名：1420462013

访问量：3401

签　名：

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

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

　　自我简介：

TA的其他文章

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

你可能喜欢

A+B for Input-Output Practice (VI) （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语言程序设计教程（第三版）课后习题7.1 （C语言代码）

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

Hello, world! （C语言代码）

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

不容易系列（C语言代码）

递增三元组（C代码）

评论区

精彩推荐

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

数组输出（C语言代码）

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

矩阵乘法（C++代码）

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

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

printf基础练习2 （C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

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

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

charmmm

TA的其他文章

你可能喜欢

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

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

Hello, world! （C语言代码）

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

不容易系列 （C语言代码）

递增三元组（C代码）

评论区

精彩推荐

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

数组输出 （C语言代码）

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

矩阵乘法 （C++代码）

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

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

printf基础练习2 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

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

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

不容易系列（C语言代码）

　　评论区

数组输出（C语言代码）

矩阵乘法（C++代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

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