帮我写一个c语言P1713 士兵排队问题代码
时间: 2023-08-28 07:16:46 浏览: 92
好的,请参考以下 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
int a[MAXN + 1];
int c[MAXN + 1];
int lowbit(int x) {
return x & (-x);
}
void update(int x, int v, int n) {
while (x <= n) {
c[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += c[x];
x -= lowbit(x);
}
return res;
}
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 离散化
int b[MAXN + 1];
for (int i = 1; i <= n; i++) {
b[i] = a[i];
}
qsort(b + 1, n, sizeof(int), cmp);
int m = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
}
// 树状数组求逆序对
long long ans = 0;
for (int i = 1; i <= n; i++) {
ans += i - 1 - query(a[i]);
update(a[i], 1, m);
}
printf("%lld\n", ans);
return 0;
}
```
该代码使用了树状数组来求解逆序对数,时间复杂度为 $O(n\log n)$,可以通过 P1713 士兵排队问题 这道题。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)