很高興在完全沒有參考任何代碼的前提下通過(guò)此題，呵呵，就是代碼比較猥瑣，跑得也比較慢，2700MS,超過(guò)時(shí)限的一半了。
此題應(yīng)該還有繼續(xù)提升的空間，我想了想，insert函數(shù)和query其實(shí)是可以放在一起的。另外網(wǎng)上的方法用了反素?cái)?shù) 這樣可以減少插入的次數(shù)，應(yīng)該也能剪去一下時(shí)間。下次試試。^_^
順便用此題做為POJ 500題紀(jì)念
#include<iostream>
using namespace std;
int n,k;
struct person
{
char s[10];
int p;
}a[500010];
int dp[500010];
void init()
{
int i,j;
for(i=1;i<=500000;i++)
for(j=1;i*j<=500000;j++)
dp[i*j]++;
}
const int maxn=500010;
struct node
{
int l,r;
int cnt;
}tree[maxn*3];
void build(int k,int l,int r)
{
tree[k].l=l;tree[k].r=r;
tree[k].cnt=0;
if(l==r) return;
int mid=(l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
}
void insert(int i,int k)
{
tree[i].cnt++;
if(tree[i].l==tree[i].r) return;
else
{
int mid=(tree[i].l+tree[i].r)>>1;
if(k<=mid)
insert(i*2,k);
else
insert(i*2+1,k);
}
}
int query(int i,int k)
{
if(tree[i].cnt==0&&tree[i].r-tree[i].l+1==k)
return tree[i].r;
int l=tree[i*2].r-tree[i*2].l+1-tree[i*2].cnt;
int r=tree[i*2+1].r-tree[i*2+1].l+1-tree[i*2+1].cnt;
if(k<=l)
return query(i*2,k);
else
return query(i*2+1,k-l);
}
int query2(int i,int l,int r)
{
if(tree[i].l==l&&tree[i].r==r)
return tree[i].r-tree[i].l+1-tree[i].cnt;
int mid=(tree[i].l+tree[i].r)>>1;
int res=0;
if(r<=mid)
res+=query2(i*2,l,r);
else if(l>mid)
res+=query2(i*2+1,l,r);
else
{
res+=query2(i*2,l,mid);
res+=query2(i*2+1,mid+1,r);
}
return res;
}
int main()
{
int i,j;
init();
int res=dp[1];
int mark=k;
while(scanf("%d%d",&n,&k)!=EOF)
{
int pos;
int res=dp[1];
int mark=k;
build(1,1,n);
for(i=1;i<=n;i++)
scanf("%s%d",a[i].s,&a[i].p);
int l,r;
int t=k;
pos=k;
insert(1,k);
for(i=2;i<=n;i++)
{
t=pos;
if(t>1)l=query2(1,1,t-1);
else l=0;
if(t<n) r=query2(1,t+1,n);
else r=0;
if(a[t].p%(l+r)!=0)
a[t].p%=(l+r);
else if(a[t].p>0)
a[t].p=l+r;
else
a[t].p=-(l+r);
if(a[t].p>0&&a[t].p<=r)
pos=query(1,l+a[t].p);
else if(a[t].p<0&&l+a[t].p>=0)
pos=query(1,l+a[t].p+1);
else if(a[t].p>0&&a[t].p>r)
pos=query(1,a[t].p-r);
else
pos=query(1,l+r-abs(l+a[t].p)+1);
if(res<dp[i])
{
mark=pos;
res=dp[i];
}
insert(1,pos);
}
printf("%s %d\n",a[mark].s,res);
}
return 0;
}