【Codeforces #312 div2 A】Lala Land and Apple Trees

首先，此题的大意是在一条坐标轴上，有\(n\)个点，每个点的权值为\(a_{i}\),第一次从原点开始走，方向自选(<- or ->)，在过程中，若遇到一个权值>0的点，则将此权值计入答案，并归零。当次、此方向上的所有点均为0后，输出此时的答案。

然后，进行分析:

我们很容易想到这是一个贪心，我们将正的和负的分别存入两个数组，最初的方向为: \(zhengsum > fusum ? zheng : fu\)即正负两边那边权值 > 0的点多就先往哪个方向走，然后，就成模拟题了……

Code:

#include<bits/stdc++.h>

using namespace std;

const int N = 100 + 5;

const int M = 100001;

int n,dir,l[M],r[M],lsum,rsum,ans;

int markjia[M] = {0},markjian[M] = {0};

int check()

{

    if(dir == -1)

    {

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

        {

            if(markjian[i])return i;

        }

        return 0;

    }else{

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

        {

            if(markjia[i])return i;

        }

        return 0;

    }

}

int main()

{

    scanf("%d",&n);

    int x,a;

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

    {

        scanf("%d %d",&x,&a);

        if(x < 0){x *= -1;l[x] = a,markjian[x] = 1,lsum++;}

        else r[x] = a,markjia[x] = 1,rsum++;

    }

    if(lsum >= rsum)dir = -1;

    else dir = 1;

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

    {

        if(check() == 0)break;

        if(dir == -1)

        {

            ans += l[check()];

            markjian[check()] = 0;

            dir = 1;

        }else{

            ans += r[check()];

            markjia[check()] = 0;

            dir = -1;

        }

    }

    cout << ans;

    return 0;

}

\(End.\)

巴特西

【Codeforces #312 div2 A】Lala Land and Apple Trees

【Codeforces #312 div2 A】Lala Land and Apple Trees

最新文章

热门文章