Блог пользователя 1115332213

Автор 1115332213, 12 лет назад, По-английски

This is my first blog. Today ,I'd like to talk about this problem,which is very intresting. the description of this problem is that each larger box can put smaller box in it. so this seems like recursion . you put small box into larger box,and larger boxs was put into the box larger than the larger box. It will not stop until there is only a type of box. please pay attention this sentence in the passage"
if side length of v is strictly less than the side length of u" this sentence is very important. here is the ac code: 3065086


#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; struct node{ __int64 len,num; //some sample may excced the int type, so you'd better us __int64; }box[110000]; int cmp(node a,node b) { return a.len<b.len; } int main() { int n; while(scanf("%d",&n)!=EOF){ int i; for(i=1;i<=n;i++) scanf("%I64d %I64d",&box[i].len,&box[i].num); sort(box+1,box+1+n,cmp); // you need first sort the statics by length. int sub,ans,res,j; for(i=2;i<=n;i++){ sub=box[i].len-box[i-1].len; if(sub>=15)continue; else { ans=1; for(j=1;j<=sub;j++){ ans=ans*4; if( (ans*box[i].num)>=box[i-1].num)break; //the lager boxs can hold all small boxs } if(ans*box[i].num<box[i-1].num){ //if they can't ,they need more larger boxs box[i-1].num-=ans*box[i].num; box[i].num+=box[i-1].num/ans; if(box[i-1].num%ans!=0)box[i].num++; } } } //the Interval of box[n].len is very important. ans=box[n].len; //[1,4] ans+1 //(4,16]ans+2 //(16,64]ans+3 and so on double test=(double)box[n].num-0.1; //this code is to solve this problem of interval if(box[n].num==1){printf("%d\n",ans+1);continue;} while(test>=1){ ans++; test/=4; } printf("%d\n",ans); } }

Полный текст и комментарии »

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится