zhaotianzju
BAN USERint solve(int n, vector<int> &v) {
sort(v.begin(), v.end());
int cnt = 0;
int up = 0;
int i = 0;
while (up < n) {
if (i < v.size() && v[i] <= up)
up += v[i++];
else
up += up + 1, cnt++;
}
return cnt;
}
int twoSum(vector<int> &nums, int target) {
int ans = 0;
for (int i=0; i<nums.size(); i++) {
int index = lower_bound(nums.begin()+i+1, nums.end(), target-nums[i])-nums.begin();
ans += nums.size()-index+1;
}
return ans;
}
int twoSum(vector<int> &nums, int target) {
int ans = 0;
for (int i=0; i<nums.size(); i++) {
int index = lower_bound(nums.begin()+i+1, nums.end(), target-nums[i])-nums.begin();
ans += nums.size()-index+1;
}
return ans;
}
The answers are m^n and (m+1)^n respectively. It can be calculated by mathematical induction.
- zhaotianzju August 28, 2015