2023-01-04：有三个题库A、B、C，每个题库均有n道题目，且题目都是从1到n进行编号每个题目都有一个难度值题库A中第i个题目的难度为ai 题库B中第i个题目的难度为bi 题库C中第i个题目

2023-01-04：有三个题库A、B、C，每个题库均有n道题目，且题目都是从1到n进行编号
每个题目都有一个难度值
题库A中第i个题目的难度为ai
题库B中第i个题目的难度为bi
题库C中第i个题目的难度为ci
小美准备组合出一套试题，试题共有三道题，
第一题来自题库A，第二题来自题库B，第三题来自题库C
试题要求题目难度递增，且梯度不能过大
具体地说，第二题的难度必须大于第一题的难度，但不能大于第一题难度的两倍
第三题的难度必须大于第二题的难度，但不能大于第二题难度的两倍
小美想知道在满足上述要求下，有多少种不同的题目组合
（三道题目中只要存在一道题目不同，则两个题目组合就视为不同
输入描述第一行一个正整数n, 表示每个题库的题目数量
第二行为n个正整数a1, a2,… an，其中ai表示题库A中第i个题目的难度值
第三行为n个正整数b1, b2,… bn，其中bi表示题库B中第i个题目的难度值
第四行为n个正整数c1, c2,… cn，其中ci表示题库C中第i个题目的难度值
1 <= n <= 20000, 1 <= ai, bi, ci <= 10^9。
来自美团。

答案2023-01-04：

双指针不回退+前缀和数组。
时间复杂度O(N * logN)。因为要排序。
空间复杂度O(N)。
用rust和solidity写代码。

代码用rust编写。代码如下：

use rand::Rng;

use std::iter::repeat;

fn main() {

    let mut a = vec![71, 29, 13, 74, 90, 8, 30, 25];

    let mut b = vec![72, 1, 50, 98, 86, 86, 52, 57];

    let mut c = vec![11, 24, 61, 70, 11, 90, 13, 30];

    let ans = ways2(&mut a, &mut b, &mut c);

    println!("ans = {}", ans);

    let nn: i32 = 100;

    let vv: i32 = 100;

    let test_time: i32 = 5000;

    println!("测试开始");

    for i in 0..test_time {

        let n = rand::thread_rng().gen_range(0, nn) + 1;

        let mut a = random_array(n, vv);

        let mut b = random_array(n, vv);

        let mut c = random_array(n, vv);

        let ans1 = ways1(&mut a, &mut b, &mut c);

        let ans2 = ways2(&mut a, &mut b, &mut c);

        if ans1 != ans2 {

            println!("出错了!{}", i);

            println!("ans1 = {}", ans1);

            println!("ans2 = {}", ans2);

            break;

        }

    }

    println!("测试结束");

}

// 暴力方法

// 时间复杂度O(N^3)

// 为了验证

fn ways1(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &mut Vec<i32>) -> i32 {

    let n = a.len() as i32;

    a.sort();

    b.sort();

    c.sort();

    let mut ans = 0;

    for i in 0..n {

        let mut j = 0;

        while j < n && b[j as usize] <= a[i as usize] * 2 {

            if b[j as usize] > a[i as usize] {

                let mut k = 0;

                while k < n && c[k as usize] <= b[j as usize] * 2 {

                    if c[k as usize] > b[j as usize] {

                        ans += 1;

                    }

                    k += 1;

                }

            }

            j += 1;

        }

    }

    return ans;

}

// 正式方法

// 时间复杂度O(N * logN)

fn ways2(a: &mut Vec<i32>, b: &mut Vec<i32>, c: &mut Vec<i32>) -> i32 {

    let n = a.len() as i32;

    a.sort();

    b.sort();

    c.sort();

    // B里面的记录

    let mut help: Vec<i32> = repeat(0).take(n as usize).collect();

    let mut i = 0;

    let mut l = -1;

    let mut r = 0;

    while i < n {

        while l + 1 < n && c[(l + 1) as usize] <= b[i as usize] {

            l += 1;

        }

        while r < n && c[r as usize] <= b[i as usize] * 2 {

            r += 1;

        }

        help[i as usize] = get_max(r - l - 1, 0);

        i += 1;

    }

    for i in 1..n {

        help[i as usize] += help[(i - 1) as usize];

    }

    let mut ans = 0;

    let mut i = 0;

    let mut l = -1;

    let mut r = 0;

    while i < n {

        while l + 1 < n && b[(l + 1) as usize] <= a[i as usize] {

            l += 1;

        }

        while r < n && b[r as usize] <= a[i as usize] * 2 {

            r += 1;

        }

        if r - l - 1 > 0 {

            ans += sum(&mut help, l + 1, r - 1);

        }

        i += 1;

    }

    return ans;

}

fn sum(help: &mut Vec<i32>, l: i32, r: i32) -> i32 {

    return if l == 0 {

        help[r as usize]

    } else {

        help[r as usize] - help[(l - 1) as usize]

    };

}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a > b {

        a

    } else {

        b

    }

}

// 为了测试

fn random_array(n: i32, v: i32) -> Vec<i32> {

    let mut arr: Vec<i32> = vec![];

    for _i in 0..n {

        arr.push(rand::thread_rng().gen_range(0, v));

    }

    return arr;

}

代码用solidity编写。代码如下：

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.17;

contract Hello{

    function main() public pure returns (int32){

        int32[] memory a = new int32[](8);

		a[0] = 71;

		a[1] = 29;

		a[2] = 13;

		a[3] = 74;

		a[4] = 90;

		a[5] = 8;

		a[6] = 30;

		a[7] = 25;

		int32[]  memory b = new int32[](8);

		b[0] = 72;

		b[1] = 1;

		b[2] = 50;

		b[3] = 98;

		b[4] = 86;

		b[5] = 86;

		b[6] = 52;

		b[7] = 57;

		int32[]  memory c = new int32[](8);

		c[0] = 11;

		c[1] = 24;

		c[2] = 61;

		c[3] = 70;

		c[4] = 11;

		c[5] = 90;

		c[6] = 13;

		c[7] = 30;

		int32 ans = ways2(a,b,c);

        return ans;

    }

	// 正式方法

	// 时间复杂度O(N * logN)

	function ways2(int32[] memory a, int32[] memory b, int32[] memory c) public pure returns (int32){

		int32 n = int32(int(a.length));

		sort(a);

		sort(b);

		sort(c);

		// B里面的记录

		int32[] memory help  = new int32[](uint(uint32(n)));

		int32 l = -1;

		int32 r = 0;

		for (int32 i = 0; i < n; i++) {

			while (l + 1 < n && c[uint(uint32(l + 1))] <= b[uint(uint32(i))]) {

				l++;

			}

			while (r < n && c[uint(uint32(r))] <= b[uint(uint32(i))] * 2) {

				r++;

			}

			help[uint(uint32(i))] = getMax(r - l - 1, 0);

		}

		for (int32 i = 1; i < n; i++) {

			help[uint(uint32(i))] += help[uint(uint32(i - 1))];

		}

		int32 ans = 0;

		l = -1;

		r = 0;

		for (int32 i = 0; i < n; i++) {

			while (l + 1 < n && b[uint(uint32(l + 1))] <= a[uint(uint32(i))]) {

				l++;

			}

			while (r < n && b[uint(uint32(r))] <= a[uint(uint32(i))] * 2) {

				r++;

			}

			if (r - l - 1 > 0) {

				ans += sum(help, l + 1, r - 1);

			}

		}

		return ans;

	}

	function sum(int32[] memory help, int32 l, int32 r) public pure returns (int32){

		return l == 0 ? help[uint(uint32(r))] : help[uint(uint32(r))] - help[uint(uint32(l - 1))];

	}

    function getMax(int32 a,int32 b) public pure returns (int32){

        if(a>b){

            return a;

        }else{

            return b;

        }

    }

	function sort(int32[] memory arr)public pure{

		int32 temp = 0;

		for(int32 i = 1; i <= int32(int(arr.length)) - 1; i++) {

			for(int32 j = i; j > 0; j--) {

				if(arr[uint(uint32(j - 1))] > arr[uint(uint32(j))]) {

					temp = arr[uint(uint32(j))];

					arr[uint(uint32(j))] = arr[uint(uint32(j - 1))];

					arr[uint(uint32(j - 1))] = temp;

				}else {

					//不满足条件结束循环即可

					break;

				}

			}

		}

	}

}

2023-01-04：有三个题库A、B、C，每个题库均有n道题目，且题目都是从1到n进行编号每个题目都有一个难度值题库A中第i个题目的难度为ai 题库B中第i个题目的难度为bi 题库C中第i个题目