社区讨论
离散化后只有10point,加id排序直接用100point,不理解
P1966[NOIP 2013 提高组] 火柴排队参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo7p6lqd
- 此快照首次捕获于
- 2023/10/27 05:29 2 年前
- 此快照最后确认于
- 2023/10/27 05:29 2 年前
。学习过程中,使用离散化,一直得10point,
按照题解加id再排序就100,看答案是离散化答案更大。
为什么?
CPP#include "cstdio"
#include "algorithm"
using namespace std;
#define RR =read()
#define int long long
#define lowbit(x) (x)&-(x)
const int M = 1e5+10,mod=1e8-3;
int a[M],aa[M],b[M],bb[M],c[M],d[M],n,ans;
struct ll{
int s,id;
}l1[M],l2[M];
bool cmp(ll a,ll b){
if(a.s!=b.s)return a.s<b.s;
return a.id<b.id;
}
void merge_sort(int l,int r){ //并归求每个元素交换次数 CDQ 陈丹琦
if(r-l<=1)return;
int mid = l+(r-l)/2;
merge_sort(l,mid);
merge_sort(mid,r);
//merge
int i=l,j=mid,k=0;
while(i<mid and j<r)
if(c[i] <= c[j] )
d[k++]=c[i++];
else
ans=(ans+(j-l)-k)%mod,
d[k++]=c[j++];
while(i<mid)
d[k++]=c[i++];
while(j<r)
d[k++]=c[j++];
for(i=l,k=0;i<r;i++,k++)c[i]=d[k];
}
int read(){
int b=0,d=1;char c=getchar();
while(c<'0' or c>'9'){
if(c=='-')d=-1;
c=getchar();
}
while('0'<=c and c<='9'){
b=b*10+c-'0';
c=getchar();
}
return b*d;
}
signed main(){
n RR;
// for(int i=1;i<=n;i++)l1[i].s RR,l1[i].id=i;
// for(int i=1;i<=n;i++)l2[i].s RR,l2[i].id=i;
// sort(l1+1,l1+1+n,cmp);
// sort(l2+1,l2+1+n,cmp);
// for(int i=1;i<=n;i++)c[l1[i].id]=l2[i].id;
for(int i=1;i<=n;i++)a[i] RR,aa[i]=a[i];
for(int i=1;i<=n;i++)b[i] RR,bb[i]=b[i];
sort(aa+1,aa+1+n);
sort(bb+1,bb+1+n);
int id_a,id_b;
for(int i=1;i<=n;i++){
a[i]=lower_bound(aa+1,aa+n+1,a[i])-aa;
b[i]=lower_bound(bb+1,bb+n+1,b[i])-bb;
}
for(int i=1;i<=n;i++)c[a[i]]=b[i];
merge_sort(1,n+1);
printf("%lld",ans%mod);
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...