2018 年蓝桥杯B组 递增三元组--------------C语言—菜鸟级

题意： 标题：递增三元组

给定三个整数数组
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN]，
请你统计有多少个三元组(i, j, k) 满足：

1. 1 <= i, j, k <= N
2. Ai < Bj < Ck

【输入格式】
第一行包含一个整数N。
第二行包含N个整数A1, A2, … AN。
第三行包含N个整数B1, B2, … BN。
第四行包含N个整数C1, C2, … CN。

对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

【输出格式】
一个整数表示答案

【样例输入】
3
1 1 1
2 2 2
3 3 3

【样例输出】
27

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
思路： 先对 a[] 与 c[] 快排一波 用an[] ,cn[]分别统计 a[]中 某元素 前（包含本身及其小于这数）的数的个数 和从c[]中某元素 后（包含本身及其大于这个数）的数的个数 在枚举 b[i] b[i]=an[d]*cn[d1] (d<b[i]<d1)

#include<stdio.h>
#include <string.h>
#define N 100004

long int n,anmin=0,cnmax=0,tn=0;
long int an[N],cn[N];
void swp(long int *t,long int x,long int y)
   {   long int tem=t[x];
      t[x]=t[y];
      t[y]=tem;
   }
long int  qp(long int t[N],long int r,long int l)
{
	long int x=t[r];
	long int i=r;
	long int j=l+1;
	while(1)
	{

		while(t[++i]<x&&i<l);
		while(t[--j]>x);
		if(i<j)swp(t,i,j);
		else break;
	}
	swp(t,r,j);
	return j;
	
}
void ppp(long int *t,long int r,long int l)
{
	long int m;
	if(r<l)
	{  m=qp(t,r,l);
	  ppp(t,r,m-1);
	  ppp(t,m+1,l);
	}
}
int main()
{long int i,j,sum=0;
long int a[N],b[N],c[N];
memset(an,0,sizeof(an));
memset(cn,0,sizeof(cn));
scanf("%ld",&n);
for(i=1;i<=n;i++)
{ scanf("%ld",&a[i]);
 if(anmin>a[i]||i==1)anmin=a[i];
}
 
for(i=1;i<=n;i++)
scanf("%ld",&b[i]);
for(i=1;i<=n;i++)
{ scanf("%ld",&c[i]);
 if(cnmax<c[i])cnmax=c[i];
}
ppp(a,1,n);
ppp(c,1,n);
for(i=1;i<=n;i++)
{
	if(an[a[i]])an[a[i]]++;//相同 就加一即可
	else an[a[i]]=i;//通过排序后的位置得出 此数前面大的个数
	j=n-i+1;
	if(cn[c[j]])cn[c[j]]++;
	else cn[c[j]]=n+1-j;//通过排序后的位置得出 此数后面大的个数
	
}


for(i=1;i<=n;i++)
{   long int d=b[i]-1;
   long int d1=b[i]+1;
	while(an[d]==0&&d>=anmin)d--;
	while(cn[d1]==0&&d1<=cnmax)d1++;
	sum+=an[d]*cn[d1];
}
printf("%ld\n",sum);
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
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/79833112