题干：
Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.
From the top view each magical box looks like a square with side length equal to 2k(k is an integer, k ≥ 0) units. A magical box v can be put inside a magical box u, if side length of v is strictly less than the side length of u. In particular, Emuskald can put 4 boxes of side length 2k - 1 into one box of side length 2k, or as in the following figure:
Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.
Input
The first line of input contains an integer n (1 ≤ n ≤ 105), the number of different sizes of boxes Emuskald has. Each of following n lines contains two integers ki and ai (0 ≤ ki ≤ 109, 1 ≤ ai ≤ 109), which means that Emuskald has ai boxes with side length 2ki. It is guaranteed that all of ki are distinct.
Output
Output a single integer p, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2p.
Examples
Input
2 0 3 1 5
Output
3
Input
1 0 4
Output
1
Input
2 1 10 2 2
Output
3
Note
Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.
In the second test case, we can put all four small boxes into a box with side length 2.
题目大意：（练习读题）
已知一个盒子(2^k)可以套四个小盒子（不能套和自己一样大的盒子！）
如果一个盒子的边长大于另一个盒子，那么这个盒子就能够容纳那另一个盒子 。
问用多大边长的正方形盒子，能够容纳所有给出的盒子。（也就是，如果全程一个盒子，需要再来一个盒子！读题！）
第一行给出总共盒子数n，下面n行，每行两个整数，分别代表盒子的大小 和 该大小盒子的盒子数量。（其中第一个盒子是用2的幂次给出。）
解题报告：
这题我好像做麻烦了，，本来想直接用数组下标代表2的幂次来着，，数量1e9的话也就是说幂次也就几百而已。。但是发现是幂次是2e9（也就是说这题全程在用幂次，跟具体数字完全无关了），，所以就不能直接用数组了，，考虑用map离散化一波，，不算难写但是还是有坑的，比如不能直接除以4，，因为不一定相邻两个大小的盒子一定是大小相差1的，，仔细理解下就能看出来。（其实看了标解后发现不需要存数据的，，直接on_process一波就ok了）
AC代码1：（直接on出结果的）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
map<ll,ll> mp;
int main()
{
int n;
ll ans = 0;
ll num,tmp,k;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%lld%lld",&k,&num);
if(num == 1) k++;
while(num > 1) {
tmp = num%4 == 0 ? num/4 : num/4+1;
num = tmp;
k++;
}
ans = max(ans,k);
}
printf("%lld\n",ans);
return 0 ;
}
/*
2
0 3
1 5
*/ AC代码2：（map处理的）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
map<ll,ll> mp;
int main()
{
int n;
ll tmp,num;
ll ans = 0;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%lld",&tmp);
scanf("%lld",&num);
ans = max(ans,tmp);
mp[tmp] += num;
}
map<ll,ll> :: iterator it = mp.begin(),end=mp.end(),ii;
--end;
for(;it != end; ++it) {
num = it->se;
++it;
ii=it;
--it;
ll pp = pow(4,ii->fi - it->fi);
tmp = num%pp == 0 ? num/pp : num/pp + 1;
++it;
if(it->se < tmp) {
it->se += (tmp - it->se);
}
--it;
}
num = end->se;
if(num == 1) {
printf("%lld\n",ans+1);
return 0 ;
}
while(num >= 4) {
tmp = num%4 == 0 ? num/4 : num/4 + 1;
num=tmp;
ans++;
}
ll out = num == 1 ? ans : ans+1;
if(out==0) out=1;
printf("%lld\n",out);
return 0 ;
} 总结： 掌握那种tmp=的那种方式，，经常需要处理一波（记得那次那个记忆化dp的计算几何题处理边的时候就需要这样来着、、）
京公网安备 11010502036488号