C. Letters （前缀和、二分查找）

浅浅的花香味﹌ 2021-12-12 09:39 215阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/978/C][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 }

转载于:https://www.cnblogs.com/-Ackerman/p/11167072.html

[http_codeforces.com_problemset_problem_978_C]: http://codeforces.com/problemset/problem/978/C