首页 > 试题广场 >

三元组

[编程题]三元组
  • 热度指数：1151 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给你一个长度为n的序列A，你需要算出有多少个三元组(Ai，Aj,Ak)满足i<j<k且AiAjAk。


输入描述:
第一行一个整数n，表示序列A的长度。
接下来一行n个整数，第i个数表示Ai的值。


输出描述:
一个整数x，表示满足要求的三元组数量。
示例1

输入

6
2 3 5 4 3 3

输出

6

说明

第1个数据为样例。
第2~4个数据范围：
n<=500，Ai<=1000000
第5~7个数据范围：
n<=2000，Ai<=1000000
第8~10个数据范围：
n<=100000，Ai<=1000000
算法知识视频讲解
添加回答
pein531头像 pein531
这个题我真的服了，10个测试用例只有一个是示例中按空格分隔数组的格式，还有9个都是把数组换行输入的，对于我这种喜欢用缓冲流读取数据的考生真是神坑，只能用Scanner了
这个题思路不是很难，主要就是遍历数组，让数组中的元素挨个成为三元组的中间元素，然后用二分法寻找小于等于它和大于等于它的数，构成单调不减的三元组。 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> used = new ArrayList<>();       // 已使用数据
        ArrayList<Integer> standby = new ArrayList<>();    // 待使用数据
        int[] arr = new int[n + 1];
        for(int i = 0; i < n; i++) {
            arr[i + 1] = sc.nextInt();
            if(i == 0)
                used.add(arr[i + 1]);
            else
                standby.add(arr[i + 1]);
        }
        Collections.sort(standby);
        long res = 0L;
        for(int i = 2; i <= n; i++){
            // 以arr[i]作为中间数
            int minIdx = upper_bound(used, arr[i]);       // 从小索引的数据中找到第一个大于arr[i]的位置
            int maxIdx = lower_bound(standby, arr[i]);    // 从大索引的数据中找到第一个大于等于arr[i]的位置
            long count1 = minIdx;                         // minIdx前面的数都可以作为三元组的最小数
            long count2 = standby.size() - maxIdx - 1;    // maxIdx后面的数都可以作为三元组的最大数
            res += count1 * count2;          // 累加上以arr[i]为中间数时的三元组数
            used.add(minIdx, arr[i]);
            standby.remove(maxIdx);
        }
        System.out.println(res);
    }
    
    private static int lower_bound(ArrayList<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        int res = right + 1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(list.get(mid) >= target){
                right = mid - 1;
                res = mid;
            }else{
                left = mid + 1;
            }
        }
        return res;
    }
    
    private static int upper_bound(ArrayList<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        int res = right + 1;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(list.get(mid) > target){
                right = mid - 1;
                res = mid;
            }else{
                left = mid + 1;
            }
        }
        return res;
    }
}

编辑于 2021-09-03 13:24:05 回复(3)
C.C.K.头像 C.C.K.
归并排序
发表于 2021-08-26 10:29:52 回复(2)
牛客658970523号头像 牛客658970523号 




import java.io.*; 
public  class Main{
        public static void main(String[] args) throws Exception {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            int n= Integer.parseInt(br.readLine());
            int[] arr=new int[n];
            String[] sp=br.readLine().split(" ");
            for (int i = 0; i <n ; i++) {
                arr[i]=Integer.parseInt(sp[i]);
            }
            int ans= process(3,0,Integer.MAX_VALUE,arr);
            System.out.println(ans);
        }
        public static int process(int rest , int i , int preChose , int[] arr){
            if (rest==0){
                return 1;
            }
            if (i>=arr.length){
                return 0;
            }
            if (preChose!=Integer.MAX_VALUE&& preChose>arr[i]){
                return 0;
            }
            int res=0;//返回的答案
            int p1=process(rest-1,i+1,arr[i],arr);
            int p2=process(rest,i+1,preChose,arr);
            res=p1+p2;
            return res;
        }
    }

发表于 2022-02-03 20:16:53 回复(2)
寒冰-侠客头像 寒冰-侠客
先上一个70分代码，复杂度n^2 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,ans=0,a[100005],dp[100005];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        for(j=i-1;j>=1;j--) 
        {/**<暴力检查a[i]左侧有多少个比a[i]小的，这个数字记录在dp[i],
            dp存储的是以i为的第二个元素的二元组个数 */
            if(a[j]<=a[i])
                dp[i]++,ans+=dp[j];/**< 顺路计算a[i]左侧a[j]的二元组，这些二元组和a[i]可以构成三元组 */
        }
    }
    cout<<ans;
    return 0;
}
可优化的就是内层循环，由于题目ai数据范围为1000000，考虑用树状数组存储和查询比a[i]小元素个数，用另一个树状数组存储二元组个数. 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,t1[1000005],t2[1000005],ans=0,a[100005];
void add1(int x,int y)
{
    for(;x<=1000000;x+=x&-x)
        t1[x]+=y;
}
ll get1(int x)
{
    ll an=0;
    for(;x;x-=x&-x)
        an+=t1[x];
    return an;
}
void add2(int x,int y)
{
    for(;x<=1000000;x+=x&-x)
        t2[x]+=y;
}
ll get2(int x)
{
    ll an=0;
    for(;x;x-=x&-x)
        an+=t2[x];
    return an;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];/**< a1为a[i]左侧不大于它的元素个数，a2为a[i]左侧二元组的个数 */
        ll a1=get1(a[i]),a2=get2(a[i]);
        add2(a[i],a1);/**< a1个元素和a[i]构成二元组，存储到t2数组 */
        add1(a[i],1);/**< 把a[i]值存储在t1数组，用于后序查询 */
        ans+=a2;
    }
    cout<<ans;
    return 0;
}


发表于 2021-10-08 20:40:51 回复(0)
机智的大魔王在写bug头像 机智的大魔王在写bug
思路是 遍历 nums[i], 比nums[i] 小的有s个，比nums[i]大的有l个
ans +=  s * l   就行了
最后3个例子答案太大溢出了变成负数
long ans = 0;
ans +=  long (s) * long(l) 
最后还是负数，有谁知道怎么解决吗
发表于 2023-08-05 15:41:54 回复(1)
善良的强盗头像 善良的强盗 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n =  in.nextInt();
        LinkedList<Integer> trank = new LinkedList<>();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = in.nextInt();
        backtrank(nums,0,trank);
        System.out.println(res);

    }
    static int res = 0;
    static void backtrank(int[] nums, int start,LinkedList<Integer> trank){
        if((trank.size() + nums.length - start ) < 3)
            return;
        if(trank.size() == 2){
            if(trank.get(0) > trank.get(1))
                return;
        }
        if(trank.size() == 3) {
            if (trank.get(0) <= trank.get(1) && trank.get(1) <= trank.get(2)) {
                res++;
            }
            return;

        }
        if(trank.size() > 3)
            return;

        for (int i = start; i < nums.length; i++) {
            trank.addLast(nums[i]);
            backtrank(nums,i + 1,trank);
            trank.removeLast();
        }
    }
}
超时了 只会回溯的方法 后面的用例太大了
发表于 2022-09-12 19:36:46 回复(0)
肥肥的哈哈头像 肥肥的哈哈
利用归并排序来辅助完成 
#include <iostream>
#include <vector>
using namespace std;
struct Data{
    //值
    int val;
    //左边比他小的
    int lsmall;
    //右边比他大的
    int rbig;
    Data():val(0), lsmall(0), rbig(0){}
};
void merge(vector<Data> &v, int l, int m, int r){
    int i = l, j = m + 1;
    vector<Data> help(r - l + 1);
    int small = 0;
    int index = 0;
    while (i <= m && j <= r){
        if (v[i].val <= v[j].val){
            v[i].rbig += (r - j + 1); 
            help[index++] = v[i];
            ++i;
            ++small;
        }else{
            v[j].lsmall += small;
            help[index++] = v[j];
            ++j;
        }
    }
    while (i <= m){
        help[index++] = v[i++];
    }
    while (j <= r){
        v[j].lsmall += small;
        help[index++] = v[j];
        ++j;
    }
    for (index = 0; index < (int)help.size();){
        v[l++] = help[index++];
    }
}
void f(vector<Data> &v, int l, int r){
    if (l >= r){
        return;
    }
    int mid = l + ((r - l) >> 1);
    f(v, l, mid);
    f(v, mid + 1, r);
    merge(v, l, mid, r);
}
void f(vector<Data> &v){
    if (v.size() < 2){
        return;
    }
    f(v, 0, v.size() - 1);
}
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<Data> v(n);
    for (int i = 0; i < n; ++i){
        cin >> v[i].val;
    }
    f(v);
    ll ans = 0;
    for (Data elem : v){
        ans += (ll)elem.lsmall * elem.rbig;
    }
    cout << ans << endl;
    return 0;
}

发表于 2021-11-29 14:07:27 回复(0)
提交观点

问题信息

微众银行 运维工程师 测试开发工程师 测试工程师 安全工程师 2021 Java工程师
上传者：小小
难度：
7条回答 3140浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号