首页 > 代码库 > POJWho Gets the Most Candies?
POJWho Gets the Most Candies?
这题想了好久才弄懂,首先题意是要求最先出队且获得的糖果数最多的人,所以只需要在循环中每次判断此时出队的人获得的糖果数是否比别人多
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include<math.h> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 555555 int card[maxn],sum[maxn<<2],F[maxn]; char name[maxn][100]; int n,k; void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { sum[rt]=1; return ; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int key,int l,int r,int rt) { if(l==r) { sum[rt]=0; k=l; return ; } int m=(l+r)>>1; if(key<=sum[rt<<1]) update(key,lson); else update(key-sum[rt<<1],rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) { return sum[rt]; } int m=(l+r)>>1; int ans=0; if(L<=m) ans+=query(L,R,lson); if(R>m) ans+=query(L,R,rson); return ans; } int main() { for(int i=1;i*i<=maxn;i++)//打出因子数量表 { for(int j=i+1;j*i<=maxn;j++) { F[i*j]+=2; } F[i*i]++; } while(scanf("%d%d",&n,&k)!=EOF) { build(1,n,1); for(int i=1;i<=n;i++) { scanf("%s%d",name[i],&card[i]); } int now=k,m=n; int maxc=0,ans=0; int left,right; for(int i=1;i<=n;i++) { update(now,1,n,1);//剩下的第now个人出队 if(F[i]>maxc)//判断是否需要更新 { maxc=F[i]; ans=k; } if(i==n) break; m--; if(card[k]%m==0)//找出下一个人是此时出队人右边第几个 { if(card[k]>0) card[k]=m; else card[k]=1; } else { card[k]%=m; if(card[k]<0) card[k]+=m+1; } left=query(1,k,1,n,1);//左边人数 right=m-left;//右边人数 if(card[k]<=right)//找出下一个出对人是此时队伍中第几个人 { now=left+card[k]; } else { now=card[k]-right; } } printf("%s %d\n",name[ans],maxc); } return 0; }
POJWho Gets the Most Candies?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。