题目地址:http://www.51cpc.com/web/problem.php?id=4286
解法 1:
1 #include<iostream> 2 #include<map> 3 using namespace std; 4 5 #define LL long long 6 map<LL, LL> imap; 7 int n; 8 9 int main() 10 { 11 ios::sync_with_stdio(false); 12 while(cin>>n) { 13 LL a,b; 14 for(int i=0; i<n; i++) { 15 cin>>a>>b; 16 imap[a] += b; 17 } 18 19 LL ans=0, last=0; 20 map<LL, LL>::iterator iter = imap.begin(); 21 for(; iter!=imap.end(); iter++) { 22 map<LL, LL>::iterator p = ++iter; 23 iter--; 24 25 LL one=iter->first, two=max(iter->second, last); 26 if(p == imap.end()) { 27 ans = one+1; 28 two = two/4 + (two%4==0?0:1); 29 while(two > 1) { 30 two = two/4 + (two%4==0?0:1); 31 ans++; 32 } 33 break; 34 } 35 36 last=two; 37 while(one < p->first) { 38 one++; 39 last = last/4 + (last%4==0?0:1); 40 if(last == 1) break; 41 } 42 } 43 cout<<ans<<endl; 44 imap.clear(); 45 } 46 47 return 0; 48 }
解法 2:机智的解法
1 #include <cstdio> 2 #include <iostream> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 const int MAXN=2e5+5; 7 struct Node 8 { 9 int w,cnt; 10 }data[MAXN]; 11 int main() 12 { 13 int n; 14 while(scanf("%d",&n)!=EOF) 15 { 16 int ans=0; 17 for(int i=0;i<n;i++) 18 { 19 cin>>data[i].w>>data[i].cnt; 20 int tot=1; 21 for(int j=data[i].w+1;;j++) 22 { 23 tot*=4; 24 if(tot>=data[i].cnt) 25 { 26 ans=max(ans,j);break; 27 } 28 } 29 } 30 cout<<ans<<endl; 31 } 32 ret
解法 3:这个简直超神了。。看到这个瞬间就清醒了,就是求4的多少次,特判下0的情况就行;
1 #include<cstdio> 2 #include<cmath> 3 int N,R=0,T,K,A; 4 main(){ 5 scanf("%d",&N); 6 while(N--){ 7 scanf("%d%d",&K,&A); 8 A=ceil(log2(A)/2); 9 K+=1>A?1:A; 10 R=R<K?K:R; 11 } 12 printf("%d",R); 13 }