浙江网站建设优化,电销系统哪个好,全国住房城乡建设厅网站,设计素材网站哪个最好用遍历三层循环,数据量十分地大,可以找第一行小于第二行的 再找第三行大于第二行的,所有方案的和
通过分析测试样例,111,222,333这三个数存在重复计算。可以想办法存一下每个数的出现次数 如果是111666999.不管1和9怎么变,只要第一行小于6,第二行小于9,答案不变 所以可以想办法存…
遍历三层循环,数据量十分地大,可以找第一行小于第二行的 再找第三行大于第二行的,所有方案的和
通过分析测试样例,111,222,333这三个数存在重复计算。可以想办法存一下每个数的出现次数 如果是111666999.不管1和9怎么变,只要第一行小于6,第二行小于9,答案不变 所以可以想办法存一下出现次数的前缀和 import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;public class Main{static int n;static int N 100010;static int[] a new int[N];static int[] b new int[N];static int[] c new int[N];static int[] cnt new int[N]; //存储数组中每个数出现的次数static int[] s new int[N]; //存储次数的前缀和static int[] as new int[N]; //有多少个数比第i个数小static int[] cs new int[N]; //有多少个数比第i个数大static BufferedReader in new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException {n Integer.parseInt(in.readLine());//存储输入数据String[] x in.readLine().split( );String[] y in.readLine().split( );String[] z in.readLine().split( );//为了方便,可以从下标1的位置开始读取存储的数据//最后 1 是因为后面的s[b[i] - 1] 会出现下标越界的情况//把所有读入的值统一 1for (int i 1; i n; i) {a[i] Integer.parseInt(x[i - 1]) 1;b[i] Integer.parseInt(y[i - 1]) 1;c[i] Integer.parseInt(z[i - 1]) 1;}//cnt[i] : 表示a[i] 中每个数出现的个数for (int i 1; i x.length; i) cnt[a[i]];//s[i] : 表示 a数组每个数出现次数的前缀和//前缀和的限制条件要用i N//比如只有3个数,但这三个数可能大于3for (int i 1; i N; i) s[i] cnt[i] s[i - 1];//as[i] 表示 a[i] 中 有多少个数比 b[i]小//也就是 用s[x] 表示,s[x]表示 x的数有多少个//不能取等 所以 x b[i] - 1//也就是as[i] s[b[i] - 1]//注意题目给的数据是无序的for (int i 1; i x.length; i) as[i] s[b[i] - 1];Arrays.fill(s,0);Arrays.fill(cnt,0);//cnt[i] : 表示c[i] 中每个数出现的个数for (int i 0; i z.length; i) cnt[c[i]];//s[i] : 表示 c数组每个数出现次数的前缀和for (int i 1; i N; i) s[i] cnt[i] s[i - 1];//要统计有多少个数比c[i]大,s[i]的含义是有多少个比i小的数//要统计比c[i]大的数,可以用s[N - 1] - s[b[i]]来算for (int i 1; i z.length; i) cs[i] s[N - 1] - s[b[i]];//最后通过as[i] 和 cs[i] 相乘 再相加就可以得到结果long sum 0;for (int i 1; i n; i) sum (long)as[i] * cs[i];System.out.println(sum);in.close();}}
