hdu 3015 树状数组+离散化
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct data
{
__int64 order;
__int64 orign;
__int64 rank;
};
data heigh[100100], coor[100100];
int cmp(const void *a, const void *b)
{
return ( (*(data *)a).order - (*(data *)b).order );
}
int cmp1(const void *a, const void *b)
{
return (*(data *)a).orign - (*(data *)b).orign;
}
/*__int64 cmp1(const void *a, const void *b)
{
}*/
int main()
{
freopen("read.txt", "r", stdin);
__int64 n;
while(~scanf("%d", &n) )
{
for(int i=1; i<=n; i++)
{
scanf("%I64d", &coor[i].orign);
scanf("%I64d", &heigh[i].orign);
coor[i].order = i;
heigh[i].order = i;
}
qsort(coor, n, sizeof(coor[0]), cmp1);
qsort(heigh, n, sizeof(heigh[0]), cmp1);
int sign1, sign2, flag1, flag2;
sign1 = sign2 = 1;
flag1 = coor[1].orign, flag2 = heigh[1].orign;
for(int i=1; i<=n; i++)
{
if(coor[i].orign != flag1)
{
flag1 = coor[i].orign;
coor[i].rank = i+1;
sign1 = i+1;
}
else
coor[i].rank = sign1;
if(heigh[i].orign != flag2)
{
flag2 = heigh[i].orign;
heigh[i].rank = i+1;
sign2 = i+1;
}
else
heigh[i].rank = sign2;
}
//qsort(coor, n, sizeof(coor[0]), cmp);
//qsort(heigh, n, sizeof(heigh[0]), cmp);
//前面是对的, 但是我不知道怎么离散化。
}
return 0;
}
附件列表
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。