感染(low) Description

n户人家住在一条直线上，从左往右依次编号为1，2，…，n。起初，有m户人家感染了COVID-19，而接下来的每天感染的人家都会感染他家左右两家的人，问t天后总共有多少人家会感染。

Input 第一行输入三个整数n(1 <= n <= 2e5)，m(0 <= m <= n)，t(1<= t <= 2e5)。

第二行m个整数ai(1 <= ai <= n)，代表最初感染的m户人家的编号。

Output 输出一个整数，代表最后会有多少人家感染。

思路

用 bfs 搜一遍

代码

#include<iostream>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define ll long long

const int Len = 2e5 + 5;

int n,m,t;

int map[Len];

int pos[Len];

int mov[2] = {-1, 1};

int mark[Len];

struct Node

{

    int x,t;

} st, ed;

queue<Node> q;

void bfs()

{

    //初始化、做标记、压队列

    while(! q.empty())

    {

        st = q.front();

        q.pop();

        if(st.t > t)

            continue;

        for(int i = 0; i < 2; i ++)

        {

            ed.x = st.x + mov[i];

            ed.t = st.t + 1;

            if(ed.x >= 1 && ed.x <= n && ! mark[ed.x] && ed.t <= t)

            {

                q.push(ed);

                mark[ed.x] = 1;

            }

        }

    }

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> m >> t;

    for(int i = 1; i <= m; i ++)

    {

        cin >> pos[i];

        mark[pos[i]] = 1;

        q.push( (Node){ pos[i], 0});

    }

    bfs();

    int cnt = 0;

    for(int i = 1; i <= n; i ++)

        if(mark[i])

            cnt ++;

    cout << cnt << endl;

    return 0;

}

Sample Input 1

10 3 2

1 3 4

Sample Output 1

6

思路

用二分

代码

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

const int Len = 1e6 + 5;

long long sum[Len];

int n,q;

int Binary_search(int k, int l, int r)

{

    int mid;

    int ans = 1e9;

    while(l <= r)

    {

        mid = (l + r) / 2;

        if(sum[mid] < k)

        {

            l = mid + 1;

        }

        else if(sum[mid] >= k)

        {

            r = mid - 1;

            ans = min(ans, mid);

        }

    }

    return ans ;

}

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    cin >> n >> q;

    for(int i = 1; i <= n; i ++)

    {

        cin >> sum[i];

        sum[i] += sum[i - 1];

    }

    int x;

    while(q --)

    {

        cin >> x;

        cout << Binary_search(x, 1, n) <<endl;

    }

    return 0;

}

思路

二分 + 维护单调队列优化

代码

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

const int Len = 1e6 + 5;

ll ar[Len];

ll br[Len];

ll sum[Len];

ll q[Len];

int id[Len];

int main()

{

    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("T.txt","r",stdin);

    int n,m;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++)

        cin >> ar[i];

    for(int i = 1; i <= n; i ++)

        cin >> br[i];

    for(int i = 1; i <= n; i ++)

        sum[i] = ar[i] - br[i] + sum[i - 1];

    int cnt = 0;

    q[++ cnt] = 0;

    id[cnt] = 1;

    for(int i = 1; i <= n; i ++)

        if(sum[i] > q[cnt])

        {

            q[++cnt] = sum[i];

            id[cnt] = i;

        }

    int tem;

    while(m --)

    {

        cin >> tem;

        cout << id[lower_bound(q + 1, q + 1 + cnt, tem) - q] << endl;

    }

    return 0;

}

巴特西

感染(low)bfs 、感染(mid) 二分、感染(high) 二分 + 维护单调队列去除无用的点

感染(low) Description

思路

代码

思路

代码

思路

代码

最新文章

热门文章

巴特西

感染(low)bfs 、感染(mid) 二分、感染(high) 二分 + 维护单调 队列去除无用的点

感染(low) Description

思路

代码

思路

代码

思路

代码

最新文章

热门文章

感染(low)bfs 、感染(mid) 二分、感染(high) 二分 + 维护单调队列去除无用的点