茂名营销型网站制作公司,成都设计网站,深圳广告公司排行,建设网站的一般过程《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
单…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
单峰数组” 链接
http://oj.ecustacm.cn/problem.php?id1839 题目描述
【题目描述】 本题对单峰数组的定义 前一部分递增后一部分递减注意每部分可以为空即完全递增、完全递减的数组也称为单峰数组。 现在给你一个长度为n的数组每次可以交换相邻两个数字请输出最小交换次数使得数组变成本题定义的单峰数组。 【输入格式】 输入第一行为正整数n1≤n≤300000。 接下来n行每行一个数字ai表示数组a1≤ai≤1000000000。 输入数字各不相同。 【输出格式】 输出一个数表示答案。 【输入样例】
8
7
4
8
10
1
2
6
9【输出样例】
7题解 如何操作才能以最小交换次数获得单峰数组显然最小的数字肯定要挪到最左边或最右边那么应该挪到左边还是右边为了使挪动次数最少应该挪到交换次数少的那一边。最小的数字处理完后面不用再管它。下一步挪第二小的数同样挪到最左边或最右边。依次这样从小到大处理所有的数直到结束。这样操作的交换次数肯定最少。 样例{7 4 8 10 1 2 6 9}的操作步骤如下 1挪最小的1。挪到最左边需要交换4次挪到最右边需要交换3次取挪到右边的3次。新序列是{7 4 8 10 2 6 9 1}因为1不用再管去掉1新序列是{7 4 8 10 2 6 9}。 2挪新序列中最小的2。挪到最左边需4次挪到最右边只需2次取2次。去掉2新序列是{7 4 8 10 6 9}。 … 依次操作一共交换321100007次。 如果用暴力法做以上操作挪动每个数是 O ( n ) O(n) O(n)复杂度的挪n个数是 O ( n 2 ) O(n^2) O(n2)的超时。 本题用树状数组求解代码简单、效率高计算复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)的。 用到的技术有离散化和树状数组具体做法参考 《算法竞赛》“4.2.3 树状数组扩展应用”的“2. 偏序问题逆序对 离散化” 几乎一样。
【笔记】 离散化、树状数组 。
C代码 #includebits/stdc.h
using namespace std;
const int N 300000 10;
int a[N], olda[N], tree[N], pos[N];
#define lowbit(x) ((x) - (x))
void update(int x, int d){ //修改元素a[x], a[x] a[x] dwhile(x N)tree[x] d, x lowbit(x);
}
int sum(int x){ //查询前缀和返回前缀和sum a[1] a[2] ... a[x]int ans 0;while(x)ans tree[x], x - lowbit(x);return ans;
}
int main(){int n; cin n;for(int i 1; i n; i)cin a[i], olda[i] a[i];sort(olda 1, olda 1 n);for(int i 1; i n; i){//离散化,得到新数组a[]a[i] lower_bound(olda 1, olda 1 n, a[i]) - olda;pos[a[i]] i; //记录每个数字的idxupdate(i, 1); //初始化树状数组树状数组的下标是这里的idx}long long ans 0;for(int i 1; i n; i) {int idx pos[i];int before sum(idx - 1); //利用树状数组求beforeint after n - i - before;ans min(before, after); //贪心挪到最左或最右update(idx, -1); //更新树状数组}coutansendl;return 0;
}
Java代码
import java.util.*;public class Main {static final int N 300000 10;static int[] a new int[N], olda new int[N], tree new int[N], pos new int[N];public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for(int i 1; i n; i) {a[i] sc.nextInt();olda[i] a[i];}Arrays.sort(olda, 1, n 1);for(int i 1; i n; i) {//离散化,得到新数组a[]a[i] Arrays.binarySearch(olda, 1, n 1, a[i]);if(a[i] 0) a[i] -a[i] - 1;pos[a[i]] i; //记录每个数字的idxupdate(i, 1); //初始化树状数组树状数组的下标是这里的idx}long ans 0;for(int i 1; i n; i) {int idx pos[i];int before sum(idx - 1); //利用树状数组求beforeint after n - i - before;ans Math.min(before, after); //贪心挪到最左或最右update(idx, -1); //更新树状数组}System.out.println(ans);}static void update(int x, int d) { //修改元素a[x], a[x] a[x] dwhile(x N) {tree[x] d;x lowbit(x);}}static int sum(int x) { //查询前缀和返回前缀和sum a[1] a[2] ... a[x]int ans 0;while(x 0) {ans tree[x];x - lowbit(x);}return ans;}static int lowbit(int x) {return x (-x);}
}Python代码
N 300000 10
a, olda, tree, pos [0] * N, [0] * N, [0] * N, [0] * N
def update(x, d): #修改元素a[x], a[x] a[x] dglobal treewhile x N:tree[x] dx lowbit(x)
def sum(x): #查询前缀和返回前缀和sum a[1] a[2] ... a[x]global treeans 0while x 0:ans tree[x]x - lowbit(x)return ans
def lowbit(x): return x (-x)
n int(input())
for i in range(1, n1):a[i] int(input())olda[i] a[i]
olda sorted(olda[1:n1])
for i in range(1, n1): a[i] olda.index(a[i]) 1 # 离散化, 得到新数组a[]pos[a[i]] i # 记录每个数字的idxupdate(i, 1) # 初始化树状数组树状数组的下标是这里的idx
ans 0
for i in range(1, n1):idx pos[i]before sum(idx - 1) # 利用树状数组求beforeafter n - i - beforeans min(before, after) # 贪心挪到最左或最右update(idx, -1) # 更新树状数组
print(ans)
