Cyber Language（签到题）

题目描述：
给定n行字符串，每个字符串中有由空格隔开的单词，把每行各个单词的首字母大写输出

input：
3 （n）
kan kan
dai dai wo
shen me wan yi

output：
KK
DDW
SMWY

解：
每行的第一个单词首字母大写输出，
之后碰到空格并且空格之后还有单词就输出空格之后第一个单词首字母

#include
using namespace std;
int main() {
    int t;
    cin >> t;
    string strs;
    getchar();//把第一行输入t之后的换行符消除
    for (int i = 0; i < t; i++) {
        getline(cin, strs);
        printf("%c", toupper(strs[0]));//每行第一个单词首字母大写
        for (int i = 1; i < strs.length(); i++) {
            if (strs[i] == ' ' && i + 1 < strs.length()) {
                printf("%c", toupper(strs[i + 1]));//遇到空格之后的下一个字母大写
            }
        }
        cout << endl;
    }
}

Taxi

题目描述：
有n个城镇，每个城镇的坐标为（xi，yi），并且每个城镇都有一个值wi，小明站在（a，b）点，求在n个城镇中选择一个城镇，使得min（|xi-a|+|yi-b|，wi）最大。

input:
1 （样例数）
3 4 （n，q）
1 5 7 （xi，yi，wi）
5 1 6
2 3 9
1 5 （a，b）
2 2
4 3
10 10

output:
6
4
5
9

解：
根据曼哈顿距离，由于|x|=max（-x，x）

所以分别记录每个点xi + yi、xi − yi、−xi + yi、−xi − yi的最大值就可以很快求出（a，b）点到每个点的曼哈顿距离最大值。
在此基础上，我们构造一个从1到n，w递增，d（曼哈顿距离）减的序列。如何构造？—>在按照w排序后从后往前遍历，第k个点中保留着k-n中所有点xi + yi、xi − yi、−xi + yi、−xi − yi的最大值，就能o(1)的时间复杂度求出（a，b）点到k-n点中最远的曼哈顿距离d。
按照二分的方法枚举城镇mid，如果w>=d,那么mid-n之间的城镇对答案的贡献至少为d，由于d是递减的，所以区间定位[1，mid-1],同理可分析w<d时区间定位[mid+1,n]

#include
using namespace std;
long long n, q, x, y, wei;
struct town {
    //用于储存i-n之间最大值
    long long x_add_y;
    long long x_y;
    long long y_x;
    long long _y_x;
    long long w;
} towns[100005];
long long cmp(town a, town b) {//w从小到大的排序
    return a.w < b.w;
}
void solve2() {//对于每次查询，二分寻找结果
    long long a, b;
    cin >> a >> b;
    long long l = 1, r = n, mid;
    long long d, res = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        d = max(max(a + b + towns[mid]._y_x, a - b + towns[mid].y_x),
                max(b - a + towns[mid].x_y, -a - b + towns[mid].x_add_y));
        if (d <= towns[mid].w) {
            res = max(res, d);//每次都保证找到的值更大才更新
            r = mid - 1;
        } else {
            res = max(towns[mid].w, res);////每次都保证找到的值更大才更新
            l = mid + 1;
        }
    }
    cout << res << endl;
}
void solve() {
    cin >> n >> q;
    for (long long i = 1; i <= n; i++) {
        cin >> x >> y >> wei;
        towns[i].w = wei;
        towns[i].x_add_y = x + y;
        towns[i]._y_x = -x - y;
        towns[i].x_y = x - y;
        towns[i].y_x = y - x;
    }
    sort(towns + 1, towns + 1 + n, cmp);
    long long max_x_add_y = INT32_MIN;
    long long max_x_y = INT32_MIN;
    long long max_y_x = INT32_MIN;
    long long maxfuyfux = INT32_MIN;
    for (long long i = n; i >= 1; i--) {//从后往前，每个点中的四个信息分别更新为i-n中信息的最大值
        max_x_add_y = max(max_x_add_y, towns[i].x_add_y);
        max_x_y = max(max_x_y, towns[i].x_y);
        max_y_x = max(max_y_x, towns[i].y_x);
        maxfuyfux = max(maxfuyfux, towns[i]._y_x);
        towns[i].x_add_y = max_x_add_y;
        towns[i].x_y = max_x_y;
        towns[i].y_x = max_y_x;
        towns[i]._y_x = maxfuyfux;
    }
    for (long long i = 1; i <= q; i++) {
        solve2();
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Package Delivery

题目描述：
有n个快递，每次最多只能拿k个，给出每个快递到达时间和最晚取走时间，求出最少取快递的次数

input：
1 （样例总数）
4 2（n k，接下来n行每行输入到达时间和最晚取走时间）
1 3
2 4
6 7
4 7

output：
2

解：
两个排列，第一个排列是根据r升序排列，第二个排列是根据l升序排列。
从r最小的区间开始记为i，接着枚举l最小的区间记为j，
如果j.l<i.r，又因为r是最小的那个，所以j区间一定会和i区间重合，我们每次找到一个重合的区间就将它加到堆中去，直到区间不重合。
在一堆重合的区间中，我们当然会选择最晚取走时间较小的先拿走，这样就不会对后面的区间造成影响，所以堆中是按照最晚取走时间升序排序的，我们取走k个区间即可，同时对取走的区间进行标记。然后问题就可以循环解决了。
在看标程时有一个疑惑，已经放到堆中的区间，如果拿走k个区间后，剩下的区间怎么办？
其实对后面的选取没有影响，i会来到没有被拿取的区间，堆中的区间都是会和i重叠的，j继续走就好了

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

#define N 100005

int l[N], r[N];
pair<int, int> p[N];
bool view[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int cmpl(int i, int j) {
    return p[i].first < p[j].first;
}

int cmpr(int i, int j) {
    return p[i].second < p[j].second;
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    int n, k, cnt;
    while (t--) {
        cnt = 0;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> p[i].first >> p[i].second;
            l[i] = i;
            r[i] = i;
            view[i] = false;
        }
        sort(l + 1, l + 1 + n, cmpl);//l升序排列,l中记录的都是按左端点从小到大排序后对应的区间编号
        sort(r + 1, r + 1 + n, cmpr);//r升序排列
        for (int i = 1, j = 1; i <= n; i++) {//先从r最小的开始找起，并从l最小的开始枚举
            if (view[r[i]]) continue;//如果已经拿掉了，continue
            while (j <= n) {//从j开始往后枚举
                if (p[l[j]].first <= p[r[i]].second) {//遇到重叠的就加入堆中
                    pq.push(pair<int, int>(p[l[j]].second, l[j]));
                    j++;
                } else {//碰到第一个不重叠的，break
                    break;
                }
            }
            cnt++;//拿取次数++
            for (int x = 1; x <= k; x++) {//在堆中的都是可以拿的，在堆中拿k件（如果够）
                if (pq.empty()) {
                    break;
                }
                view[pq.top().second] = true;//拿过的标记
                pq.pop();
            }
        }
        cout << cnt << endl;
    }

}