I - The hat

题意：
n个人编号1到n坐一圈，每个人手上有一个数字ai，任意相邻两个人的数字之差为1或-1,现在你有询问方式? x，机器会回答你x编号的人手上的数字。你的任务是找到任意一个人跟其对面人手上数字相同的人，并回答! ans，ans为满足条件的人，如果没有这样的人，回答! -1
题解：
手写一个样例找规律，可以看出每个人的数字与其对面的数字之差是一个单调的序列且只为0，2，-2，二分找出差为零的位置。
注：当n=4k+2时，每个人跟其对面的人之间相差2k+1个人，因为任意相邻两个人的数字之差为1或-1，而且2k+1为奇数，那么对面的人跟他经过奇数次+1或-1之后现在不可能是跟他相同数字，所以n=4k+2的情况一定无解。

#include<iostream>
using namespace std;
int n,k=0;
bool Judge(int x) {
    int cx = (x + n / 2) % n,vx,vcx;
    if ((x + n / 2) == n)
        cx = n;
    cout << "? " << x << endl;
    cout << "? " << cx << endl;
    cin >> vx >> vcx;
    if (vx - vcx == 0) {
        cout << "! " << x << endl;
        k = 1;
    }
    if (vx - vcx > 0)
        return true;
    else
        return false;
}
int main() {
    cin >> n;
    if (n % 4)
        cout << "! -1" << endl;
    else {
        int l = 1, r = 1 + n / 2, mid;
        bool dir = Judge(l),dir1;
        while (l + 1 < r) {
            if (k)
                break;
            mid = (l + r) / 2;
            dir1 = Judge(mid);
            if (dir) {
                if (dir1)
                    l = mid;
                else
                    r = mid;
            }
            else {
                if (dir1)
                    r = mid;
                else
                    l = mid;
            }
        }
    }
}

J - Resource Distribution

题意：
给出n个服务器的资源数c1,c2,...,cn和运行2个程序需要的资源x1,x2求一个解决方案满足
1.选取k1个资源数不小于x1,k1的服务器使资源总和不小于x1
2.选取k2个资源数不小于x2,k2的服务器使资源总和不小于x2
3.两次选取的服务器不能有交叉
题解：
对服务器按资源升序排序，从小到大枚举k1，二分找到第一个资源大于等于X1/k1的服务器，设其位置为p，如果p + k1 - 1 <=n,说明p及之后的k1个服务器均可分配x1，此时的k1也是最小的。 找到p后，我们不妨固定最后k1个服务器分配x1，即将[p, p + k1 - 1]后移至[n - k1 + 1, n]，以便最大限度分配x2,然后同上分配x2.

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 500;
int n;
double x1,x2,temp;
struct Node
{
    int id;
    double v;
}node[maxn];
bool cmp(Node a, Node b) {
    return a.v < b.v;
}
bool Judge1(int cnt1, double x2)
{
    for (int cnt2 = 1; cnt2 <= n - cnt1; cnt2++) {
        double p2 = x2 / cnt2;
        int q = lower_bound(node + 1, node + n + 1, Node{ 0, p2 },cmp) - node;
        if (q + cnt1 + cnt2- 1 <= n) {
            cout << "Yes" << endl;
            cout << cnt1 << " " << cnt2 << endl;
            for (int i = n - cnt1 + 1; i <= n; i++)
                cout << node[i].id<<' ';
            cout << endl;
            for (int i = q; i <= q + cnt2 - 1; i++)
                cout << node[i].id << ' ' << endl;
            cout << endl;
            return true;
        }
    }
    return false;
}
bool Judge2(int cnt2, double x1)
{
    for (int cnt1 = 1; cnt1 <= n - cnt2; cnt1++) {
        double p1 = x1 / cnt1;
        int p = lower_bound(node + 1, node + n + 1, Node{ 0, p1 },cmp) - node;
        if (p + cnt1 + cnt2 - 1 <= n) {
            cout << "Yes" << endl;
            cout << cnt1 << " " << cnt2 << endl;
            for (int i = p; i <= p + cnt1 - 1; i++)
                cout << node[i].id <<" ";
            cout << endl;
            for (int i = n - cnt2 + 1; i <= n; i++)
                cout << node[i].id<<" ";
            cout << endl;
            return true;
        }
    }
    return false;
}
int main() {
    cin >> n >> x1 >> x2;
    for (int i = 1; i <= n; i++)
    {
        node[i].id = i;
        cin >> node[i].v;
    }
    sort(node + 1, node + 1 + n, cmp);
    int cnt1 = 1,seat,cnt2=1;
    for (; cnt1 <= n-1; cnt1++)
    {
        temp = x1 / cnt1;
        seat = lower_bound(node + 1, node + n + 1, Node{ 0,temp },cmp) - node;
        if (seat + cnt1 - 1 <= n)
            break;
    }
    for (; cnt2 <= n - 1; cnt2++)
    {
        temp = x2 / cnt2;
        seat = lower_bound(node + 1, node + n + 1, Node{ 0,temp },cmp) - node;
        if (seat + cnt2 - 1 <= n)
            break;
    }
    if (!Judge1(cnt1, x2) && !Judge2(cnt2, x1))
        cout << "No" << endl;
}