好老师

题目描述
我想当一个好老师，所以我决定记住所有学生的名字。可是不久以后我就放弃了，因为学生太多了，根本记不住。但是我不能让我的学生发现这一点，否则会很没面子。所以每次要叫学生的名字时，我会引用离他最近的，我认得的学生。比如有10个学生：
A ? ? D ? ? ? H ? ?
想叫每个学生时，具体的叫法是：

输入
输入只有一组数据。第一行是学生数n（1<=n<=100）。第二行是每个学生的名字，按照从左到右的顺序给出，以逗号分隔。每个名字要么是不超过3个英文字母，要么是问号。至少有一个学生的名字不是问号。下一行是询问的个数q（1<=q<=100）。每组数据包含一个整数p（1<=p<=n），即要叫的学生所在的位置（左数第一个是位置1）。

输出
对于每个询问，输出叫法。注意"middle of X and Y"只有当被叫者离有两个最近的已知学生X和Y，并且X在Y的左边。

样例输入
10
A ? ? D ? ? ? H ? ?
4
3
8
6
10
样例输出
left of D
H
middle of D and H
right of right of H

思路
这是一个模拟题，只需要按照题目意思模拟一遍即可，但是要注意数组越界以及选左选右的情况判定，当我们询问的时候，如果这个学生恰好是认识的，那就直接输出他的名字，如果不记得这个学生的名字那么我们就要分三步去讨论，我们就从询问的学生开始左边遍历一次，直到遇到记得的学生的名字为止，如果在遍历之后依然没有记得的学生的名字那么就把一个无穷大的值赋给那个变量，这方便后面的比较，说明老师记得学生的名字可能在右边。往右遍历同理。最后一种情况就是左右记得的学生姓名距离相等那么就按照题目的意思输出即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 0x3f3f3f3f;
char a[110][4];
int main()
{
   
    int n, q, m;
    while (~scanf("%d", &n))
    {
   
        for (int i = 1; i <= n; ++i)
            scanf("%s", a[i]);
        scanf("%d", &q);
        while (q--)
        {
   
            scanf("%d", &m);
            if (a[m][0] != '?') //字符串的首字母判断
                printf("%s\n", a[m]);
            else
            {
   
                int right = m, left = m, rr = 0, ll = 0;//初始化
                while (a[right][0] == '?')//向右遍历，，下同
                {
   
                    right++;
                    rr++;
                    if (right > n)//如果越界了那么就赋给它一个无穷大的数，，下同
                    {
   
                        rr = maxn;
                        break;
                    }
                }
                while (a[left][0] == '?')
                {
   
                    left--;
                    ll++;
                    if (left < 1)
                    {
   
                        ll = maxn;
                        break;
                    }
                }
                if (ll == rr)
                    printf("middle of %s and %s\n", a[left], a[right]);
                if (ll > rr)
                {
   
                    for (int i = 1; i <= rr; ++i)
                        printf("left of ");//要注意空格
                    printf("%s\n", a[right]);
                }
                if (ll < rr)
                {
   
                    for (int i = 1; i <= ll; ++i)
                        printf("right of ");
                    printf("%s\n", a[left]);
                }
            }
        }
    }
    return 0;
}

高桥与低桥

题目描述
有个脑筋急转弯是这样的：有距离很近的一高一低两座桥，两次洪水之后高桥被淹了两次，低桥却只被淹了一次，为什么？答案是：因为低桥太低了，第一次洪水退去之后水位依然在低桥之上，所以不算“淹了两次”。举例说明：
假定高桥和低桥的高度分别是5和2，初始水位为1
第一次洪水：水位提高到6（两个桥都被淹），退到2（高桥不再被淹，但低桥仍然被淹）
第二次洪水：水位提高到8（高桥又被淹了），退到3。
没错，文字游戏。关键在于“又”的含义。如果某次洪水退去之后一座桥仍然被淹，那么下次洪水来临水位提高时不能算“又”淹一次。
输入n座桥的高度以及第i次洪水的涨水水位ai和退水水位bi，统计有多少座桥至少被淹了k次。初始水位为1，且每次洪水的涨水水位一定大于上次洪水的退水水位。

输入
输入文件最多包含25组测试数据。每组数据第一行为三个整数n, m, k（1<=n,m,k<=105）。第二行为n个整数hi（2<=hi<=108），即各个桥的高度。以下m行每行包含两个整数ai和bi（1<=bi<ai<=108, ai>bi-1）。输入文件不超过5MB。

输出
对于每组数据，输出至少被淹k次的桥的个数。

样例输入
2 2 2
2 5
6 2
8 3
5 3 2
2 3 4 5 6
5 3
4 2
5 2
样例输出
Case 1: 1
Case 2: 3

ps：
这个题目竟然用二分去做！！！
在此之前我用的暴力一个一个去判断，很显然会超时！所以我wa了6发，可怜之人必有可恨之处，蒟蒻的我还不太熟悉二分，在得知代码时候，竟然连代码有看了一个多小时才看懂，这个题目有前缀和的思想。所以我决定做一篇深刻的题解，欢迎各位acmer指出不足。
首先，我们把桥的高度先按照从小到大（从大到小也行）排序，这样方便后面统计，这时候我们用二分去搜索桥的高度，我们把每次被水淹没的第一个桥加一，把第一个不被淹没的桥进行减一操作，相当于左区间加一右区间减一，这样就很方便我们用前缀和求解问题，我手动举个例子，比如sum[i] 数组1 1 1 -1 -2这分别对应第1 2 3 4 5座桥，第一座桥被淹没了一次，第二座桥加上前面那次就被淹没了两次…以此类推就可以求出第几座桥被淹没了几次，那么就是1, 2，3, 2，0不得不说这是一个好方法，这也是一个好题目。在代码里面我们可以用STL的自带的二分函数
lower_boundupper_bound/函数
STL 自带的二分函数—— upper_bound 和 lower_bound。
这两个函数的作用是二分查找一个数在数组中出现的位置。区别是 upper 返回第一个大于搜索数的位置，而 lower 是第一个大于等于的数的位置。显然这道题用的是 lower。
函数的用法：lower_bound(a.begin(),a.end(),x) 返回第一个大于等于 x 的数的地址。而由于是地址，在最后要 −a（也就是减去地址）。
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中，

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], sum[maxn];
int main()
{
   
   int n, m, k, ca = 0;
   while (~scanf("%d%d%d", &n, &m, &k))
   {
   
      memset(h, 0, sizeof(h));
      memset(sum, 0, sizeof(sum));
      for (int i = 0; i < n; ++i)
         scanf("%d", &h[i]);
      sort(h, h + n);
      int num = 1;
      while (m--)
      {
   
         int a, b;
         scanf("%d%d", &a, &b);
         int left = lower_bound(h, h + n, num + 1) - h;
         int right = lower_bound(h, h + n, a + 1) - h;
         num = b;
         sum[left]++;
         sum[right]--;
         // cout << left << ' ' << right << endl;
      }
      int ans = 0, cur = 0;
      // for (int i = 0; i < n; ++i)
      // cout << sum[i] << endl;
      for (int i = 0; i < n; ++i)//前缀和思想
      {
   
         cur += sum[i];
         if (cur >= k)
            ans++;
      }
      printf("Case %d: %d\n", ++ca, ans);
   }
   return 0;
}