POJ 2886 Who Gets the Most Candies?（树状数组+二分）
最后更新于：2022-04-01 15:53:14
题目链接：[点击打开链接](http://poj.org/problem?id=2886)
题意：一共n个人， 从第k个人开始， 这个人离队并且指定向左或向右第v个人离队， 依次下去， 求得分最高的人是谁。
第p个人离队， 将得到G（p）分， G（p）是可以整除p的所有数。
对于可以被i整除的数的个数， 我们可以通过枚举每一个数的倍数， 预先处理出来。
该题直接模拟就好， 因为每次都一定有一个人出队， 所以要枚举n次 ， 对于每次， 要计算具体是哪个人出队， 这个可以用数学推导很快的算出来是当前队列的第几个人， 要找到这个人我们可以用二分+树状数组来优化算法。
复杂度O(n*logn*logn)
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 500000 + 10;
int T,n,k,m,cnt[maxn] = {0},bit[maxn];
struct node {
char s[20];
int v;
}a[maxn];
int sum(int x) {
int ans = 0;
while(x > 0) {
ans += bit[x];
x -= x & -x;
}
return ans;
}
void add(int x, int d) {
while(x <= n) {
bit[x] += d;
x += x & -x;
}
}
void init() {
for(int i=1;i<=500000;i++) {
for(int j=i;j<=500000;j+=i) {
cnt[j]++;
}
}
}
int erfen(int x) {
int l = 1, r = n, mid;
while(r > l) {
mid = (r + l) >> 1;
if(sum(mid) >= x) r = mid;
else l = mid + 1;
}
return r;
}
int main() {
init();
while(~scanf("%d%d",&n,&k)) {
memset(bit, 0, (n+1)*sizeof(bit[0]));
int maxv = cnt[1];
for(int i=1;i<=n;i++) {
scanf("%s%d",a[i].s,&a[i].v);
maxv = max(maxv, cnt[i]);
add(i, 1);
}
int now = k, nxt = k, _cnt = 1;
while(true) {
int nn = n - _cnt;
m = a[now].v;
if(cnt[_cnt] == maxv) {
printf("%s %d\n",a[now].s,cnt[_cnt]); break;
}
if(m > 0) nxt = (nxt - 1 + m % nn) % nn;
else nxt = ((nxt + m)%nn + nn)%nn;
if(nxt == 0) nxt = nn;
add(now, -1);
now = erfen(nxt);
_cnt++;
}
}
return 0;
}
~~~