标签：怎么 int == print 顺序 数组 排序 sort printf
原OJ提交点这里
这道题一开始让我很雾......
不过 思路其实非常清晰：如果i具体操作也很好实现：
定义一个结构体 x升序排列 当x相同就y升序排列
按照我们的排序方式 把a[i].y踢出来跑树状数组求逆序对就可以了
附上AC代码
#include
#include
#include
#include
#includeusing namespace std;
const int N=1005;
int l,n,m,k,c[1005],a[1005];
long long ans=0;
struct nodee
{
int x,y;
}qwq[N*N];
int lowbit(int x)
{
return x&-x;
}
void add(int pos,int x)
{
for(int i=pos;ilowbit(i))
{
c[i]+=x;
}
}
int query(int pos)
{
long long sum=0;
for(int i=pos;i>=1;i-=lowbit(i))
{
sum+=c[i];
}
return sum;
}
bool cmp(nodee a,nodee b)
{
return (a.xb.y));
}
int main()
{
scanf("%d",&l);
for(int i=1;i)
{
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
scanf("%d%d%d",&n,&m,&k);
for(int j=1;j)
{
scanf("%d%d",&qwq[j].x,&qwq[j].y);
}
sort(qwq+1,qwq+1+k,cmp);
ans=0;
for(int j=k;j>=1;j--)
{
add(qwq[j].y,1);
ans+=query(qwq[j].y-1);
}
printf("Test case %d: %lld\n",i,ans);
}
return 0;
}
最后还是要插两句 我开始的逆序对用了离散化 并且在最后求逆序对跑的顺序 不知道为什么 在luogu,Virtual Judge和POJ都是RE，后来还变成了TLE（好过分嘤嘤嘤） 我不知道这是怎么肥四！ 这道题应该可以跑归并 我没有尝试 大家有兴趣可以试试 贴一下我RE的代码 至今不知道错在哪 欢迎大佬指正
#include
#include
#include
#include
using namespace std;
const int N=10005;
int l,n,m,k,c[N],a[N];
long long ans=0;
struct node
{
int tot,num;
}qaq[N];
struct nodee
{
int x,y;
}qwq[N];
int lowbit(int x)
{
return x&-x;
}
void add(int pos,int x)
{
for(int i=pos;i1005;i+=lowbit(i))
{
c[i]+=x;
}
}
int query(int pos)
{
long long sum=0;
for(int i=pos;i>=1;i-=lowbit(i))
{
sum+=c[i];
}
return sum;
}
bool cmp(nodee a,nodee b)
{
return (a.xb.y));
}
bool cmpp(node a,node b)
{
return a.totb.tot;
}
int main()
{
scanf("%d",&l);
for(int i=1;i)
{
scanf("%d%d%d",&n,&m,&k);
for(int j=1;j)
{
scanf("%d%d",&qwq[j].x,&qwq[j].y);
}
sort(qwq+1,qwq+1+k,cmp);
for(int j=1;j)
{
qaq[j].tot=qwq[j].y;
qaq[j].num=j;
}
sort(qaq+1,qaq+1+k,cmpp);
for(int j=1;j)
{
a[qaq[j].num]=j;
}
ans=0;
for(int j=1;j)
{
add(a[j],1);
ans+=(j-query(a[j]));
}
printf("Test case %d: %lld\n",i,ans);
}
return 0;
}
题解 SP4226 【MSE06H - Japan】(树状数组+逆序对)
标签：怎么 int == print 顺序 数组 排序 sort printf
原文地址：https://www.cnblogs.com/valentino/p/11142296.html