请求撤下题解
  • 板块P1908 逆序对
  • 楼主XiaoQuQu
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/6/12 20:00
  • 上次更新2023/11/4 21:57:57
查看原帖
请求撤下题解
427623
XiaoQuQu楼主2021/6/12 20:00

rt,大佬 @zhylj 写的题解实测 #6 WA.
25oYw9.png 测试代码:

#include<algorithm>
#include<cstdio>
using namespace std;
int n, m, c[40005] = { 0 }, a[40005] = { 0 }, b[40005] = { 0 };  //定义数组,b[]为读入的数组,a[]为要离散化后的数组,C[]为树状数组
inline void Add(register int x)  //树状数组加入
{
    for (; x <= n; x += (x & -x))
        c[x]++;  //因为这里只需要1,所以我就写出c[x]++了
}
inline int Sum(register int x)  //树状数组求和,同上面的sum(x)
{
    register int s = 0;  //计数的变量
    for (; x > 0; x -= (x & -x))  //累计
        s += c[x];
    return s;  //返回结果
}
bool cmp1(const int& x, const int& y)  //离散化需要用的,上面有讲
{
    return b[x] > b[y];
}
int main()
{
    freopen("C:\\Users\\XiaoQ\\Downloads\\test.in", "r", stdin);
    int ans = 0;  //ans为最后的结果
    scanf("%d", &n);  //读入n
    for (register int i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]);  //读入
        a[i] = i;  //顺便初始化一下a数组
    }
    sort(a + 1, a + n + 1, cmp1);  //给a数组排序,达到最终的效果
    for (register int i = 1; i <= n; i++)
    {
        Add(a[i]);  //依次加入树状数组
        ans += Sum(a[i] - 1);  //计算结果并累计
    }
    printf("%d", ans);  //输出ans
    return 0;  //返回
}

(自己wa了就想把别人拖下水的屑

2021/6/12 20:00
加载中...