【二分-贪心】问题集合

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

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') 
Read the rest