POJ 2182 Lost Cows 【二分查找+树状数组】

r囧r小猫 2022-10-06 04:54 223阅读 0赞

**题目大意**

在一个1-n的排列中
    告诉你第i个数前面有多少比它小
    还原这个排列

**分析**

从后向前确定
    如果最后一个数a[n]=i
    那么表示有i个数字比 n位置小，所以n位置就是i+1
    同理 在1-n中去掉数字i+1之后变成集合s
    倒数第二个数 如果 a[n-1] = k
    那么就是在集合s中找到第k+1小的数字

开一个n+1大小的数组 初始值都是1，
    数组只有 0和1两个值 0表示已经被移除了
    sum(i)那么前n项目和表示的就是i处在排列的第几位
    例如 2 和 3 已经被移除的情况下

这个时候 就可以得到 5是第三小
    如果要找第一小
    但是2 和3 都是1 
    所以我们要找到的是sum里面第一个为1的 后面的都是被移除的
    可以使用二分查找进行，找到第一个为1的 返回下标即可
    
    更新sum可以使用树状数组，可以自行百度

#include <iostream>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    
    using namespace std;
    
    #pragma warning(disable:4996)
    #define low(x) ((x)&(-x))
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    typedef long long ll;
    
    int n;
    
    int a[8001];
    int c[8001];
    
    bool update(int pos,int v) { 
    	for (; pos <= n; pos += low(pos)) { 
    		c[pos] += v;
    	}
    	return true;
    }
    
    int getSum(int p) { 
    	int sum = 0;
    	for (; p > 0; p -= low(p)) { 
    		sum += c[p];
    		
    	}
    	return sum;
    }
    
    int nu[8001];
    
    int main() { 
    	
    	//freopen("../in1.txt","r",stdin);
    
    	cin >> n;
    
    	for (int i = 1; i <= n; ++i) { 
    		c[i] = low(i);
    	}
    
    	nu[1] = 1;
    	for (int i = 2; i <= n; ++i) { 
    		scanf("%d",&nu[i]);
    		nu[i]++;
    	}
    
    	for (int i = n; i >= 1; --i) { 
    		//debug(i)
    		int l = nu[i];
    		int r = n;
    		int f = -1;
    		while (l <= r) { 
    			int mid = (l + r) / 2;
    			int s = getSum(mid);
    			//debug(mid)
    			if (s >= nu[i]) { 
    				f = mid;
    				r = mid - 1;
    			}
    			else { 
    				l = mid + 1;
    			}
    		}
    		//debug(f)
    		a[i] = f;
    
    		update(a[i], -1);
    	}
    
    	for (int i = 1; i <= n; ++i) { 
    		cout << a[i] << endl;
    	}
    	return 0;
    }

![在这里插入图片描述][20210611105619157.png]

[20210611105619157.png]: /images/20221005/9e0af3c0b944414a8c763fde1f6e2feb.png