社区讨论
求助映射哪里出问题了
P1966[NOIP 2013 提高组] 火柴排队参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo7qoklw
- 此快照首次捕获于
- 2023/10/27 06:11 2 年前
- 此快照最后确认于
- 2023/10/27 06:11 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
#define MAXN 100005
int n,a[MAXN],b[MAXN],c[MAXN],d[MAXN],e[MAXN];
long long ret;
void Divide(int l,int r)
{
if(l==r)
return;
int m=(l+r)/2;
Divide(l,m);
Divide(m+1,r);
for(int i=l,j=m+1,k=l;i<=m||j<=r;)
if(i<=m&&(j>r||a[i]<=a[j]))
e[k++]=a[i++],ret+=j-m-1;
else
e[k++]=a[j++];
for(int i=l;i<=r;i++)
a[i]=e[i];
return ;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
c[i]=a[i]=read();
for(int i=1;i<=n;i++)
d[i]=b[i]=read();
sort(c+1,c+n+1);
sort(d+1,d+n+1);
for(int i=1;i<=n;i++)
a[i]=lower_bound(c+1,c+n+1,a[i])-c;
for(int i=1;i<=n;i++)
b[i]=lower_bound(d+1,d+n+1,b[i])-d;
for(int i=1;i<=n;i++)
a[i]=b[a[i]];
Divide(1,n);
printf("%lld\n",ret);
return 0;
}
rt,有点绕,人傻了
回复
共 1 条回复,欢迎继续交流。
正在加载回复...