C. Letters （前缀和、二分查找）
题目链接：http://codeforces.com/problemset/problem/978/C
题目的意思：告诉你几个宿舍，然后每个宿舍有多少个房间，每个房间的编号是一次从第一个加起来的，现在给你一些信封，信封上只有房间号，现在让我们判断这个房间是属于哪个宿舍，在这个宿舍里他是第几个房间。
第一种方法手写二分：
1 #include <cstdio> 2 #include <string> 3 #include <iostream> 4 #include <algorithm> 5 #include <cstdbool> 6 #include <string.h> 7 #include <math.h> 8 9 10 using namespace std; 11 12 typedef long long LL; 13 14 LL a[2000005]; 15 LL pre[2000005]; 16 17 LL binarySearch(LL a[],LL n,LL key) 18 { 19 LL left = 1,right = n-1; 20 while (left <= right) 21 { 22 LL mid = (left + right) / 2; 23 if (a[mid] >= key) 24 right = mid - 1; 25 else if (a[mid] < key) 26 left = mid + 1; 27 } 28 return left; 29 } 30 31 int main() 32 { 33 ios_base::sync_with_stdio(0); 34 cin.tie(NULL); 35 LL n,m; 36 cin >> n >> m; 37 for (LL i=1;i<=n;i++) 38 { 39 cin >> a[i]; 40 pre[i] = pre[i-1]+a[i]; 41 } 42 LL temp; 43 for (LL i=1;i<=m;i++) 44 { 45 cin >> temp; 46 LL pos = binarySearch(pre,n,temp); 47 cout << pos << ' ' << temp-pre[pos-1] << endl; 48 } 49 return 0; 50 }
第二种方法：利用C++的函数
1 #include <cstdio> 2 #include <string> 3 #include <iostream> 4 #include <algorithm> 5 #include <cstdbool> 6 #include <string.h> 7 #include <math.h> 8 9 10 using namespace std; 11 12 typedef long long LL; 13 14 LL a[2000005]; 15 LL pre[2000005]; 16 17 18 int main() 19 { 20 ios_base::sync_with_stdio(0); 21 cin.tie(NULL); 22 LL n,m; 23 cin >> n >> m; 24 for (LL i=1;i<=n;i++) 25 { 26 cin >> a[i]; 27 pre[i] = pre[i-1]+a[i]; 28 } 29 LL temp; 30 for (LL i=1;i<=m;i++) 31 { 32 cin >> temp; 33 LL pos = lower_bound(pre+1,pre+1+n,temp)-pre; 34 cout << pos << ' ' << temp-pre[pos-1] << endl; 35 } 36 return 0; 37 }
