Codeforces 558A Lala Land and Apple Trees 摘苹果

题意:n棵苹果树在x轴上排成一排,每棵苹果树有一个坐标值(均不为0)和苹果数量。现在某人从0开始任意选择一个方向走,每遇到一颗新的苹果树就摘下所有苹果,然后掉转方向直到遇到下一颗之前没遇到过的苹果树然后再摘下所有苹果,如此往复直到再也遇不到新的苹果树。问最多能摘下多少个苹果。

水题。以0为中心,对坐标排序后计算左右两边的苹果树个数。如果左边小于右边,就先从左边摘,反之则先从右边摘。最后看有多少个苹果树摘不到即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
using namespace std;

const int MAX = 105;
int n;
int x, a, sum;
vector <pair <int, int> > l, r; //懒得写结构体了

bool cmp(pair <int, int> p1, pair <int, int> p2)
{
    return p1.first < p2.first;
}

void input()
{
    l.clear();
    r.clear();
    sum = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &x, &a);
        if(x < 0)
            l.push_back(make_pair(x, a));
        else
            r.push_back(make_pair(x, a));
        sum += a;
    }
}

void solve()
{
    int ls = l.size(), rs = r.size();
    int total = abs(ls - rs) - 1; //不能摘到的苹果树棵树
    sort(l.begin(), l.end(), cmp);
    sort(r.begin(), r.end(), cmp);
    if(l.size() > r.size())
    {
        for(int i = 0; i < total; i++) //左边不能摘到的从左算起
            sum -= l[i].second;
    }
    else
    {
        for(int i = 0; i < total; i++) //右边不能摘到的从右算起
            sum -= r[r.size() - i - 1].second;
    }
    printf("%d\n", sum);
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        input();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 07-12

Codeforces 558A Lala Land and Apple Trees 摘苹果的相关文章

Codeforces 558A Lala Land and Apple Trees(Sort快排)

A. Lala Land and Apple Trees time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Amr lives in Lala Land. Lala Land is a very beautiful country that is located on a coordinate line. Lala Land is

cf 558A Lala Land and Apple Trees

#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; struct data { int x; int a; }; data l[1024],r[1024]; bool c1(data q,data p) { return q.x<p.x; } bool c2(data q,data p) { return q.x>p.x; } int main() { i

Codeforces Round #312 (Div. 2) A. Lala Land and Apple Trees 暴力

A. Lala Land and Apple Trees Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/558/problem/A Description Amr lives in Lala Land. Lala Land is a very beautiful country that is located on a coordinate line. Lala Land is famous

CF 558A(Lala Land and Apple Trees-暴力)

A. Lala Land and Apple Trees time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Amr lives in Lala Land. Lala Land is a very beautiful country that is located on a coordinate line. Lala Land is

Codeforces Round #312 (Div. 2) A.Lala Land and Apple Trees

Amr lives in Lala Land. Lala Land is a very beautiful country that is located on a coordinate line. Lala Land is famous with its apple trees growing everywhere. Lala Land has exactly n apple trees. Tree number i is located in a position xi and has ai

#5 DIV2 A POJ 3321 Apple Tree 摘苹果 构建线段树

Apple Tree Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 25232   Accepted: 7503 Description There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been

Codechef December Challenge 2014 Chef and Apple Trees 水题

Chef and Apple Trees Chef loves to prepare delicious dishes. This time, Chef has decided to prepare a special dish for you, and needs to gather several apples to do so. Chef has N apple trees in his home garden. Each tree has a certain (non-zero) num

NOIP2005-普及组复赛-第一题-陶陶摘苹果

题目描述 Description 陶陶家的院子里有一棵苹果树,每到秋天树上就会结出10个苹果.苹果成熟的时候,陶陶就会跑去摘苹果.陶陶有个30厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试. 现在已知10个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的最大高度,请帮陶陶算一下她能够摘到的苹果的数目.假设她碰到苹果,苹果就会掉下来. 输入输出格式 Input/output 输入格式:输入文件apple.in包括两行数据.第一行包含10个100到200之间(包括100和200

BZOJ 3384: [Usaco2004 Nov]Apple Catching 接苹果( dp )

dp dp( x , k ) = max( dp( x - 1 , k - 1 ) + *** , dp( x - 1 , k ) + *** ) *** = 0 or 1 ,根据情况 (BZOJ 1750双倍经验) ------------------------------------------------------------------------ #include<cstdio> #include<cstring> #include<algorithm>