Good Teacher（模拟）

Good Teacher

Time Limit:1000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

Submit Status Practice UVA 12662

I want to be a good teacher, so at least I need to remember all the student names. However, there are
too many students, so I failed. It is a shame, so I don’t want my students to know this. Whenever I
need to call someone, I call his CLOSEST student instead. For example, there are 10 students:
A ? ? D ? ? ? H ? ?
Then, to call each student, I use this table:
Pos Reference
1 A
2 right of A
3 left of D
4 D
5 right of D
6 middle of D and H
7 left of H
8 H
9 right of H
10 right of right of H
Input
There is only one test case. The first line contains n, the number of students (1 ≤ n ≤ 100). The next
line contains n space-separated names. Each name is either ‘?’ or a string of no more than 3 English
letters. There will be at least one name not equal to ‘?’. The next line contains q, the number of
queries (1 ≤ q ≤ 100). Then each of the next q lines contains the position p (1 ≤ p ≤ n) of a student
(counting from left).
Output
Print q lines, each for a student. Note that ‘middle of X and Y ’ is only used when X and Y are
both closest of the student, and X is always to his left.
Sample Input

10
A ? ? D ? ? ? H ? ?
4
3
8
6
10
Sample Output
left of D
H
middle of D and H
right of right of H

题解：老师点名，由于一些同学不认识名字，所以要找离他最近的同学代替，题中的I call his CLOSEST student instead；

还有一点就是两个同学中间，但是这两个同学间不能有人。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
string name[110];
map<int, string> ans;
int p[110];
bool js(int i){
    if(ans.count(i) == 0)
        return true;
    else 
        return false;
}
int main(){
    int n, q;
    while(~scanf("%d", &n)){
        int tp = 0;
        ans.clear();
        for(int i = 1; i <= n; i++){
            cin >> name[i];
            if(name[i] != "?"){
                ans[i] = name[i];
                p[tp++] = i;
            }
        }
        for(int i = 0; i < tp - 1; i++){
            if((p[i + 1] + p[i]) % 2 == 0 && js((p[i + 1] + p[i])/2))
                ans[(p[i + 1] + p[i])/2] = "middle of " + name[p[i]] + " and " + name[p[i + 1]];

        }
        for(int i = 1; i <= n; i++){
            if(ans.count(i) == 0){
                int x = lower_bound(p, p + tp, i) - p;
                int cnt, cnt1;
                if(x == 0){
                    cnt = p[0] - i;
                    while(cnt--){
                        ans[i] = "left of " + ans[i];
                    }
                    ans[i] += name[p[0]];
                }
                else{
                    cnt = i - p[x - 1];
                    if(x < tp)cnt1 = p[x] - i;
                    if(x == tp || cnt < cnt1){
                        while(cnt--){
                            ans[i] = "right of " + ans[i];
                        }
                        ans[i] += name[p[x - 1]];
                    }
                    else{
                        while(cnt1--){
                            ans[i] = "left of " + ans[i];
                        }
                        ans[i] += name[p[x]];
                    }
                }
            }
        }
        int q, x;
        scanf("%d", &q);
        while(q--){
            scanf("%d", &x);
            cout << ans[x] << endl;
        }
    }
    return 0;
}