跳出来的人所得到的糖果数量和他跳出的顺序有关 所得的糖果数为 (假设他是第k个跳出的) 则他得到的糖数为k能被多少个数正数 比如说 k
= 6 ;
思路:线段数 先算出N个人中,是第几个人(id)跳出来得到的糖果最多。然后模拟id遍 长到第id个人的name
线段树的结点中保存该区间内还剩多少人,每次update 删除一个人。
//24200K
1235MS
#include <stdio.h>
#include <string.h>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
const int M = 500010;
int n,id;
struct tree
{
//sum 表 该区间剩余人数
} node[M*3];
struct data
{
val;
name[15];
} boy[M];
int ans[M]; //ans[i]保存第i个人跳出能得到的糖果数量
void BuildTree (int left,int right,int u)
{
left;
right;
= right - left + 1;
right)
return ;
(left + right)>>1;
BuildTree(left,mid,L(u));
BuildTree(mid+1,right,R(u));
}
int update (int key,int u)
{
--;
(node[u].l == node[u].r)
return node[u].l;
(node[L(u)].sum >= key)
return update(key,L(u));
return update (key - node[L(u)].sum,R(u));
}
void count_ans()
{
(ans,0,sizeof(ans));
//计算ans
1; i <= n; i ++)
ans[i] ++;
for (int j = 2*i; j <= n; j += i)
ans[j] ++;
ans[1];
1;
2; i <= n; i ++) //找出第几个人跳出获得的糖最多
if (ans[i] > max)
{
max = ans[i];
id = i;
}
}
int main ()
{
i,k,mod;
(~scanf ("%d %d",&n,&k))
count_ans();
for (i = 1; i <= n; i ++)
scanf ("%s %d",boy[i].name,&boy[i].val);
BuildTree (1,n,1);
mod = node[1].sum;
int pos = 0;
boy[0].val = 0;
n = id;
while (n --)
{