首页 > 代码库 > Cows

Cows

2024-07-05 12:08:43   226人阅读

poj2481:http://poj.org/problem?id=2481

题意：有N头牛，每只牛有一个测试值[S,E]，如果对于牛i和牛j来说，它们的测验值满足下面的条件则证明牛i比牛j强壮：Si <=Sjand Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值，要求输出每头牛有几头牛比其强壮

解题：先按s值排个序(由小到大)，s值相同的按e排序（由大到小）,然后按照排好的序列对e值进行求逆序数。注意处理s和e分别相同的情况。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define lson u<<1
 6 #define rson u<<1|1
 7 using namespace std;
 8 const int N=100002;
 9 int ll[4*N],rr[4*N],sum[4*N];
10 int ans[N];
11 struct Node{
12     int x;
13     int y;
14     int id;//记录结果的顺序
15     bool operator<(const Node a)const{//排序
16        if(x<a.x)return true;
17        if(x==a.x&&y>a.y)return true;
18        return false;
19     }
20 }num[N];
21 void pushUP(int u){
22     sum[u]=sum[lson]+sum[rson];
23 }
24 void  build(int l,int r,int u){
25     ll[u]=l;
26     rr[u]=r;
27     sum[u]=0;
28     if(l==r)
29      return ;
30     int mid=(l+r)/2;
31     build(l,mid,lson);
32     build(mid+1,r,rson);
33 }
34 void update(int pos ,int u){
35     if(ll[u]==rr[u]){
36         sum[u]++;//注意这里是++，因为可能有重复的值
37         return;
38     }
39     int mid=(ll[u]+rr[u])/2;
40     if(mid>=pos)update(pos,lson);
41     else
42         update(pos,rson);
43     pushUP(u);
44 }
45 int query(int l,int r,int u){
46     if(ll[u]==l&&rr[u]==r){
47         return sum[u];
48     }
49     int mid=(ll[u]+rr[u])/2;
50     if(mid>=r)return query(l,r,lson);
51     else  if(mid<l)return query(l,r,rson);
52     else {
53         return query(l,mid,lson)+query(mid+1,r,rson);
54     }
55 }
56 int n,u,v;
57 int main(){
58      while(~scanf("%d",&n)&&n>0){
59            memset(ans,0,sizeof(ans));
60            for(int i=1;i<=n;i++){
61               scanf("%d%d",&u,&v);
62               num[i].x=u;
63               num[i].y=v;
64               num[i].id=i;
65            }
66         build(1,100000,1);//直接建100000的树，因为e的最大值就是100000
67         sort(num+1,num+n+1);//排序
68         for(int i=1;i<=n;i++){
69             int y=num[i].y;
70              if(i>=2&&num[i-1].x==num[i].x&&num[i-1].y==num[i].y)//对于重复值，不用计算，有前面的值即可得到
71                 ans[num[i].id]=ans[num[i-1].id];
72                 else
73            ans[num[i].id]=query(y,100000,1);//否则查询后面的的区间，注意要包括当前这个点，因为x值不同时，这个点是计数的
74             update(num[i].y,1);//更新
75         }
76       for(int i=1;i<n;i++)
77         printf("%d ",ans[i]);
78         printf("%d\n",ans[n]);
79      }
80 }
View Code

 


联系
我们