淄博乐达网站建设,做流量任务的试用网站,旅游网站功能流程图,莱州市招聘网站题目描述#xff1a; 小 A 现在有一个长度为 #x1d45b; 的序列 {#x1d465;#x1d456;}#xff0c;但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的#xff0c;当且仅当存在 #x1d458; ∈ [1, #x1d45b;]#xff0c;满足#xff1a; #…题目描述 小 A 现在有一个长度为 的序列 {}但是小 A 认为这个序列不够优美。 小 A 认为一个序列是优美的当且仅当存在 ∈ [1, ]满足 1 ≤ 2 ≤ … ≤ ≥ 1 ≥ … ≥ 。现在小 A 可以进行若干次操作每次可以交换序列中相邻的两个项现在他想知道最少操作多少次之后能够使序列变为优美的。
Input Format
第一行一个正整数 表示序列的长度。 接下来一行 个整数表示初始的序列。
Output Format
输出一行一个整数表示最少需要的操作次数。
Sample Input
5 3 4 1 2
Sample Output
1
Constraints
对于 30% 的数据 ≤ 12。
对于 60% 的数据 ≤ 100000, 互不相同。
对于 100% 的数据, ≤ 100000。
思路 仔细分析题意因只能交换序列中相邻的两个项且要求中间数大两端较小。可以用贪心思想将每一个小的x[i]往左或往右两端移动取最小的交换次数最后累加即为所求。其实就是计算每个数左边或右边比它大的数逆序对有多少个取最优。 用树状数组刚好能满足快速计算逆序对的需求。注意因数据有可能重复我们需要将数组从大到小排序且将数值相同的元素id大的往前放。
#includebits/stdc.h
using namespace std;
int t[100005], n;
struct node {int x, id;
} a[100005], b[100005];
bool sort1(node a, node b) { //从大到小排序值相同ID大的放前面if (a.x b.x) return a.id b.id;return a.x b.x;
}
void add(int pos, int x) {while (pos n) {t[pos] x;pos -pos pos;}
}
int sum(int pos) {int ans 0;while (pos) {ans t[pos];pos - -pos pos;}return ans;
}
int main() {int ans 0;cin n;int resa[n 1], resb[n 1];for (int i 1; i n; i) {scanf(%d, a[i].x);b[i].x a[i].x; //复制一个数组用于计算右边逆序对a[i].id i; //求i左边逆序对b[i].id n - i 1; //求i右边逆序对id取反}sort(a 1, a 1 n, sort1);sort(b 1, b 1 n, sort1);for (int i 1; i n; i) {add(a[i].id, 1);resa[a[i].id] sum(a[i].id - 1); //把每个i的逆序对保存到数组对应位置}memset(t, 0, sizeof(t)); //清空数组以便计算右边逆序对for (int i 1; i n; i) {add(b[i].id, 1);resb[b[i].id] sum(b[i].id - 1); }reverse(resb 1, resb 1 n); //之前id是反向定义需要反转数组元素for (int i 1; i n; i)ans min(resa[i], resb[i]); //取每个i对于左右逆序对的最小值的和即为所求cout ans;return 0;
}
