本文共 1163 字,大约阅读时间需要 3 分钟。
zoj题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3635
解题报告人:GHQ(SpringWater)
题目大意:每次从编号1-n删除一个数字,重新编号1-(n-1),重复操作,问你每次删除的那个编号的最初编号是?
解题思路,利用树状数组,求出第K大的编号是ans,则当前编号为k的最初编号为ans!
求最低位
int Lowbit(int t) { return t & ( t ^ ( t - 1 ) ); }
求前n项和:
int Sum(int end) { int sum = 0; while(end > 0) { sum += in[end]; end -= Lowbit(end); } return sum; } |
#include#include #define MAXN 50005int res[MAXN],c[MAXN];int find_kth(int k,int N){ int ans = 0, cnt = 0, i; for (i = 20; i >= 0; i--) { ans += (1 << i); if (ans >= N|| cnt + c[ans] >= k) ans -= (1 << i); else cnt += c[ans]; } return ans + 1;}int lowbit(int x){ return x & -x;}void add(int x, int num,int N){ for ( ; x <= N; x += lowbit(x)) c[x] += num;}int main(){ int N,K,i,num; while(~scanf("%d",&N)) { memset(c,0,sizeof(c)); for(i=1;i<=N;i++)add(i,1,N); for(i=1;i<=N;i++) { scanf("%d",&K); res[i]=find_kth(K,N); add(res[i],-1,N); } scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d",&num); if(i
转载地址:http://ahuvi.baihongyu.com/