社区讨论

离散化后只有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 条回复,欢迎继续交流。

正在加载回复...