离散化就是去一个数列的数值不重要,重要的是他们的相对位置,或者说能够用结构体把原先的信息存储下来,然后用相对位置得到新的一个下标,然后可以用线段树进行优化。举个例子,1-1000之间的1000的距离可以看做是1-2的只要1-1000之间没有影响他们相对次序的元素,1-50-100这样可以看做1-2-3;

const int maxn=1e5+10;
int a[maxn], t[maxn], b[maxn];
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
    scanf("%d",a[i]),t[i]=a[i];
sort(t+1,t+n+1);
m=unique(t+1,t+1+n)-t-1;//求出的m为不重复的元素的个数
for(int i=1; i<=n; i++)
    b[i]=lower_bound(t+1,t+1+m,a[i])-t;
//a[i]为原来的数组,b[i]为离散化后的数组

这是一种离散化,去除重复元素。

另一种包含重复元素,并且相同元素离散化后不相同,2.不包含重复元素,并且不同元素离散化后不同,符合这两种的其中一个,推荐使用

struct A
{
    int x, idx;
    bool operator < (const A &rhs) const
    {
        return x < rhs.x;
    }//也可以写个cmp函数排序
};
A a[MAXN];
int rank[MAXN];
int n;
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
{
    scanf("%d", &a[i].x);
    a[i].idx = i;
}
//for(int i=1; i<=n; i++)
//    printf("%d  %d\n",a[i].idx,a[i].x);
//printf("\n");
sort(a + 1, a + n + 1);
//for(int i=1; i<=n; i++)
//    printf("%d  %d\n",a[i].idx,a[i].x);
//printf("\n");
for(int i = 1; i <= n; ++i)
{
    rank[a[i].idx] = i;
//    printf("rank[%d] = %d\n",a[i].idx,i);
}

http://blog.csdn.net/xiangaccepted/article/details/73276826?tdsourcetag=s_pctim_aiomsg

发表评论

电子邮件地址不会被公开。 必填项已用*标注