二分这类问题 通常需要猜结论乱搞，解决此类问题的方法，就是见多识广

Q1

题意是说一个船会随风飘动，风的方向有周期。船每天也可以选择往一个方向自由航行，效果和风叠加，类似矢量。问最少多少天能到目的地。

做法是二分天数。天数定了，船如果不动，终点就是定了的。再此基础上船还可以走 天数 这么多步。如果和目的地的距离小于这个步数就缩减天数。

单调性：对于mid天，如果能达到，那么大于mid天也肯定能达到，因为多出的天数船可以想办法每天抵消风的影响呆在原地。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
int n, dirx[maxn], diry[maxn], desx, desy,inix,iniy;
string s;
int main()
{
    cin >> inix >> iniy >> desx >> desy;
    if(inix == desx && iniy == desy)
    {cout<<0;return 0;}
    cin >> n >> s;
    for(int i = 1; i <= n; i++ )
    {
        if(s[i - 1] == 'U') diry[i] = 1;
        if(s[i - 1] == 'D') diry[i] = -1;
        if(s[i - 1] == 'L') dirx[i] = -1;
        if(s[i - 1] == 'R') dirx[i] = 1;
    }
    for(int i = 2; i <= n; i++ )
    {
        dirx[i] += dirx[i - 1];
        diry[i] += diry[i - 1];
    }
    ll l = 1,r = 1LL << 63 - 1;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        ll tx = (mid / n) * dirx[n] + inix + dirx[mid % n];
        ll ty = (mid / n) * diry[n] + iniy + diry[mid % n];
        if(abs(desx - tx) + abs(desy - ty) <= mid) r = mid;
        else l = mid + 1;
    }
    if(r == 1LL << 63 - 1) cout << -1;
    else cout << l;
}

Q2

题意说有 m 个任务， n 杯咖啡，第 i 杯咖啡可以解决 ci 个任务。每天第二杯咖啡效果会 – 1 ，第二杯 – 2 以此类推。直到为 0 ，效果不能为负数。问最少多少天能完成任务。

做法是排序咖啡效果。二分天数，在天数定了的基础上每天第一杯都是效果最好的咖啡，第二杯次之……如果咖啡用完能完成任务，缩减天数。

这个其实需要考到在天数定了的情况下，每天喝更多杯咖啡不会比平均每天和一样多杯咖啡更优（(-1-2-3)(-1) < (-1-2)(-1-2)）。效果更差的排在前面不会比更好的排在前面更优（因为效果不能为负数，所以效果更差的排在后面的当他没效果的时候损失越小）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
typedef long long ll;
ll n, m;
ll a[maxn],b[maxn];
bool cmp(const int &a, const int &b)
{
    return a>b;
}
int main()
{
    ll tot = 0,cnt = 0;
    cin >> n >> m;
    for(int i = 1;i <= n; i++ )
    {
        cin >> a[i];
        tot += a[i];
        cnt ++ ;
    }
    sort(a + 1, a + 1 + n, cmp);
    if(tot < m) 
    {
        cout<< -1;
        return 0;
    }
    ll l = 1,r = n;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        ll k=1,res=0,q=0;
        while(k<=n)
        {
            for(int i=1;i<=mid;i++) 
            {
                res+=max(0LL,a[k]-q);
                k++;
                if(k>n) break;
            }
            q++;
        }
        if(res>=m) r=mid;
        else l=mid+1;
    }
    cout<< l;
}

Q3

标题即传送门