有多少三元组 NBUT - 1723

朴灿烈づ我的快乐病毒、 2023-07-17 14:13 5阅读 0赞

**Description**

有三个数组A，B，C，每个数组中有n个数，你可以从每个数组中找一个数，使得Ai<Bj<Ck ,(1<=I,j,k<=n)(1<=n<=100000,1<=Ai,Bj,Ck<=1000000)，求最多可以组出多少三元组

**Input**

有多组输入  
第一行输入n  
接下来三行输入A，B，C三个数组，每个数组n个数

**Output**

每行一个整数，表示最多有多少三元组

**Sample Input**

3
    1 1 1
    2 2 2
    3 3 3
    3
    1 2 3
    1 2 3
    1 2 3

**Sample Output**

27
    1

//#include<bits/stdc++.h>
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
     
    using namespace std;
    const int maxn=100005;
    int a[maxn],b[maxn],c[maxn];
    typedef long long ll;
    int main() { 
    	int n;
    	while(cin>>n) { 
    		ll cnt=0;
    		for(int i=0; i<n; i++) { 
    			scanf("%d",&a[i]);
    		}
    		for(int i=0; i<n; i++) { 
    			scanf("%d",&b[i]);
    		}
    		for(int i=0; i<n; i++) { 
    			scanf("%d",&c[i]);
    		}
    		sort(a,a+n);
    		sort(b,b+n);
            sort(c,c+n);
            for(int i=0;i<n;i++){ //遍历b[i]找到a中比它小，c中比它大的元素 
            	ll x=lower_bound(a,a+n,b[i])-a;//找到第一个>=b[i]的元素下标
    			ll y=upper_bound(c,c+n,b[i])-c;//找到第一个>b[i]的元素下标
    			cnt+=x*(n-y);
    		}
    		printf("%lld\n",cnt);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 NLP-信息抽取-三元组-联合抽取-TabelFilling-2022：OneRel【单模块、单步解码的实体关系联合抽取方法】【直接识别三元组、更好捕获三元组间的相互依赖】【只有N个矩阵】

实体关系抽取算是这两年比较火热的NLP任务之一，熟悉JayJay的同学们都知道，JayJay一直比较关心关系抽取的进展。过去的2年，关系抽取的SOTA也一直被追逐赶超、不断

墨蓝/ 2023年09月25日 13:54/ 0 赞/ 19 阅读

相关有多少三元组 NBUT - 1723

Description 有三个数组A，B，C，每个数组中有n个数，你可以从每个数组中找一个数，使得Ai<Bj<Ck ,(1<=I,j,k<=n)(1<=n<=100000,1

朴灿烈づ我的快乐病毒、/ 2023年07月17日 14:13/ 0 赞/ 6 阅读

相关 2016.计算机院.Problem A.三元组

问题描述给你一个长度为m的数组(数组元素从0到m-1)，如果数组里有a\[i\]+a\[j\]==ak，便称之为三元组。现在给你一个数组，让你求三元组的个数。

川长思鸟来/ 2023年07月17日 09:57/ 0 赞/ 32 阅读

相关三元组表示稀疏矩阵并相加

三元组表示稀疏矩阵并相加一、实验题目：要求稀疏矩阵用三元组结构存储，实现矩阵A+B=C,并采用矩阵形式显示结果。二、实验思路：定义两个结构体，Tri

左手的ㄟ右手/ 2023年02月20日 12:25/ 0 赞/ 55 阅读

相关【数据结构】三元组的转置

include <stdio.h> define maxsize 100 //三元组结点： typedef int datatype;

一时失言乱红尘/ 2022年08月25日 09:21/ 0 赞/ 180 阅读

相关数组和广义表的基本运算实现（三元组）

问题及代码： a：![20160530163235725][] b： ![20160530163239698][] / Copyright (c) 201

本是古典何须时尚/ 2022年08月22日 14:18/ 0 赞/ 212 阅读

相关 NBUT 1655-木块拼接【模拟】

\[1655\] 木块拼接时间限制: 1000 ms　内存限制: 65535 K 问题描述好奇的skyv95想要做一个正方形的木块，现在有三种颜

待我称王封你为后i/ 2022年08月21日 00:07/ 0 赞/ 191 阅读

相关 poj1723

include <cstdio> include <algorithm> using namespace std; const int N =

悠悠/ 2022年06月18日 04:19/ 0 赞/ 13 阅读

相关蓝桥杯递增三元组

给定三个整数数组 A = [A1, A2, ... AN], B = [B1, B2, ... BN], C = [C1, C2, ... CN]，请你统计有

蔚落/ 2022年03月10日 00:23/ 0 赞/ 225 阅读

相关 NBUT - 1220 SPY

题目衔接：[https://ac.2333.moe/Problem/view.xhtml?id=1220][https_ac.2333.moe_Problem_view.xht

快来打我*/ 2022年02月23日 05:26/ 0 赞/ 196 阅读