poj 2481 Cows


http://poj.org/problem?id=2481
Farmer John's cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.

Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John's N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].

But some cows are strong and some are weak. Given two cows: cowi and cowj, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj, we say that cowi is stronger than cowj.

For each cow, how many cows are stronger than her? Farmer John needs your help!
Input
The input contains multiple test cases.
For each test case, the first line is an integer N (1 <= N <= 105), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 105) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge.

The end of the input contains a single 0.
Output
For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cowi
Sample Input
3
1 2
0 3
3 4
0
Sample Output
1 0 0
题意是给出了一堆牛的能力值,这些能力值是用一定区间表示的。一头牛比另一头牛强壮就是这头牛的能力值区间真包含了另一头牛的能力值区间(能力值区间相等不能算作比其强壮)。问对于每一头牛来说,在这个群体中有多少头牛比自己强壮。
009   class TNode implements Comparable{
010    int s;//左端点
011    int e;//右端点
012    int label;//牛的序号
013    public int compareTo(Object o) { 
014       int v=((TNode)o).e;
015       if(this.e!=v) //按右端点降序排列
016         return v-this.e;  
017       return this.s-((TNode)o).s;//右端点相等,按左端点升序排序
018    }
019
020    public String toString(){
021        return ("["+s+","+e+"]");
022    }
023  }
024
025 public class Main{
026   static  int N=100015;
027   TNode[] cow;
028   int cal[];//树状数组
029   int res[];
030   int maxn;
031
032  public Main(){
033     
034     }
035        
036   
037
038  private int lowbit(int t){//计算cal[t]展开的项数  
039   return t&(-t);  
040  }  
041
042  private int Sum(int k){ //求前k项的和.  
043   int sum=0;   
044    while(k>0){   
045       sum+=cal[k];   
046       k=k-lowbit(k);   
047    }       
048    return sum;   
049  }   
050
051  private void update(int i,int x){    //增加某个元素的大小,给某个节点 i 加上 x  
052      while(i<=maxn){   
053        cal[i]=cal[i]+x; //更新父节点
054        i=i+lowbit(i);   
055     }   
056    }   
061  public static void  main(String args[]) throws IOException{
062        Main ma=new Main();
063        ma.go();
064   }
066    public void go() throws IOException{
067      
068      StreamTokenizer st = new StreamTokenizer(new BufferedReader(     
069      new InputStreamReader(System.in)));     
070      PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));     
071
072      while(true) {
073       st.nextToken();     
074      int n= (int) st.nval;    //牛的个数 
075      if(n==0break;
076
077     cow=new TNode[N];
078     cal=new int[N];
079     res=new int[N];
080     for(int i=0;i< N;i++){
081       cow[i]=new TNode();
082      // cal[i]=0;
083      }
084      for(int i=0;i< n;i++) {//读入牛的吃草区间
085            st.nextToken();    
086           cow[i].s=(int) st.nval;
087             st.nextToken();    
088           cow[i].e=(int) st.nval;
089           cow[i].s++;
090           cow[i].e++;
091           cow[i].label=i;//牛的原始序号
092           if(cow[i].e>maxn) maxn=cow[i].e;//最大右端点
093      }
094        
095        Arrays.sort(cow);//排序
096
097     // for(int i=0;i< n;i++)
098       // System.out.println(cow[i]);
099  
100      for(int i=0;i< n;i++) {
101           if(i!=0&&cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e)//两头牛有相同的吃草区间
102                res[cow[i].label]=res[cow[i-1].label];//它们有相同的答案
103            else res[cow[i].label]=Sum(cow[i].s);//统计比cow[i].label这头牛强的牛的数目
104            update(cow[i].s,1);//更新
105        }
106        System.out.printf("%d",res[0]);
107        for(int i=1;i< n;i++) System.out.printf(" %d",res[i]);
108        System.out.println();
109    }
110  }


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts