移动商城网站建设,魔兽做图下载网站,网站维护升级访问中,商务网站开发与建设#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1060 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图 部门组对编程问题描述输入格式输出格式样例输入样例输出样例输入样例输出数据范围题解参考代码 部门组对编程
问题描述
LYA所在的部门计划通过结对编程的方式进行项目开发。已知部门中有 n n n 名员工每个员工都有一个独特的职级。结对编程要求从部门中选出三名员工组成一个小组设这三名员工的序号分别为 i i i、 j j j、 k k k他们的职级分别为 l e v e l [ i ] level[i] level[i]、 l e v e l [ j ] level[j] level[j]、 l e v e l [ k ] level[k] level[k]则小组需要满足以下条件之一 l e v e l [ i ] l e v e l [ j ] l e v e l [ k ] level[i] level[j] level[k] level[i]level[j]level[k] l e v e l [ i ] l e v e l [ j ] l e v e l [ k ] level[i] level[j] level[k] level[i]level[j]level[k]
其中 0 ≤ i j k n 0 \le i j k n 0≤ijkn。
请你计算在满足上述条件的情况下可以组建的小组数量。注意同一员工可以参与多个小组。
输入格式
第一行输入一个正整数 n n n表示员工总数。
第二行输入 n n n 个正整数以空格分隔表示按员工序号排列的职级 l e v e l [ 0 ] level[0] level[0] 到 l e v e l [ n − 1 ] level[n-1] level[n−1]。
输出格式
输出一个整数表示可以组建的小组数量。
样例输入
4
1 2 3 4样例输出
4样例输入
3
5 4 7样例输出
0数据范围 1 ≤ n ≤ 6000 1 \le n \le 6000 1≤n≤6000 1 ≤ l e v e l [ i ] ≤ 1 0 5 1 \le level[i] \le 10^5 1≤level[i]≤105
题解
可以枚举每个员工作为小组的中间位置然后统计其左侧职级比他低的人数乘以右侧职级比他高的人数这样就能得到以该员工为中间人所能组成的小组数量。需要注意的是为了避免重复统计我们需要将所有员工按照职级从低到高或从高到低排序然后再进行统计。
具体步骤如下
读入员工总数 n n n 以及每个员工的职级 l e v e l level level。正序计算每个员工作为中间位置所能组成的小组数量 对于第 i i i 个员工统计其左侧职级比他低的人数 l e f t [ i ] left[i] left[i]。对于第 i i i 个员工统计其右侧职级比他高的人数 r i g h t [ i ] right[i] right[i]。累加 l e f t [ i ] × r i g h t [ i ] left[i] \times right[i] left[i]×right[i] 到答案中。 将员工职级序列反转然后重复步骤 2。
参考代码
Python
n int(input())
level list(map(int, input().split()))def count_groups(level):n len(level)res 0left [0] * nright [0] * nfor i in range(n):for j in range(i):if level[j] level[i]:left[i] 1for j in range(i 1, n):if level[j] level[i]:right[i] 1for i in range(n):res left[i] * right[i]return resres count_groups(level)
res count_groups(level[::-1])
print(res)Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] level new int[n];for (int i 0; i n; i) {level[i] sc.nextInt();}long res countGroups(level);res countGroups(reverse(level));System.out.println(res);}private static long countGroups(int[] level) {int n level.length;long res 0;int[] left new int[n];int[] right new int[n];for (int i 0; i n; i) {for (int j 0; j i; j) {if (level[j] level[i]) {left[i];}}for (int j i 1; j n; j) {if (level[j] level[i]) {right[i];}}}for (int i 0; i n; i) {res (long) left[i] * right[i];}return res;}private static int[] reverse(int[] level) {int n level.length;int[] res new int[n];for (int i 0; i n; i) {res[i] level[n - i - 1];}return res;}
}Cpp
#include bits/stdc.h
using namespace std;long long countGroups(vectorint level) {int n level.size();long long res 0;vectorint left(n, 0), right(n, 0);for (int i 0; i n; i) {for (int j 0; j i; j) {if (level[j] level[i]) {left[i];}}for (int j i 1; j n; j) {if (level[j] level[i]) {right[i];}}}for (int i 0; i n; i) {res (long long) left[i] * right[i];}return res;
}int main() {int n;cin n;vectorint level(n);for (int i 0; i n; i) {cin level[i];}long long res countGroups(level);reverse(level.begin(), level.end());res countGroups(level);cout res endl;return 0;
}
