uva 11039 - Building designing

点击打开链接uva 11039

思路:贪心(排序+枚举)
分析:
1 题目要求按照题目给定的数据求能够建立最高几层的楼房
2 题目要求上层的大小要比下层小,并且两层之间的颜色要交替的出现。很明显,我们只要按照size进行排序,然后枚举即可。

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 500010;
int n , Case;
struct floor{
    int color;
    int size;
    bool operator<(const floor &fl)const{
        return size > fl.size;
    }
};
floor f[MAXN];

int main(){
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d" , &n);
        for(int i = 0 ; i < n ; i++){
           scanf("%d" , &f[i].color);
           f[i].size = abs(f[i].color);
        }
        sort(f , f+n);
        int ans , preSize , preColor;
        ans = 1;
        preSize = f[0].size;
        preColor = f[0].color;
        for(int i = 1 ; i < n ; i++){
           if(f[i].color > 0){
              if(preColor < 0){
                 ans++;
                 preColor = f[i].color;
              }
           }
           else{
              if(preColor > 0){
                 ans++;
                 preColor = f[i].color;
              }
           }
        }
        printf("%d\n" , ans);
    }
    return 0;
}
时间: 2024-10-26 02:12:38

uva 11039 - Building designing的相关文章

uva11039 Building Designing

题意:给出n个数,请按照他们绝对值的递增顺序排序,且相邻元素不能有相同符号(必须一个大于0,一个小于0),问这样操作后最多有多少个元素 分析:先调用sort排序然后逐个判断相邻两个元素的乘积是否小于0.  注意结果会溢出,不能用int,可以用double,当然用bool型变量标记也可以 1 #include <stdio.h> 2 #include <iostream> 3 #include <vector> 4 #include <algorithm> 5

UVA之409 - Excuses, Excuses!

 Excuses, Excuses!  Judge Ito is having a problem with people subpoenaed for jury duty giving rather lame excuses in order to avoid serving. In order to reduce the amount of time required listening to goofy excuses, Judge Ito has asked that you write

UVa 10397:Connect the Campus (最小生成树)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338 题目: Problem E Connect the Campus Input: standard input Output: standard output Time Limit: 2 seconds Many new buildings are

UVa 539:The Settlers of Catan, 简单回溯

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=480 题目类型: 回溯法 原题: Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by buildi

SEERC 2004 / UVa 1330 City Game (扫描)

1330 - City Game Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076 Bob is a strategy game programming specialist. In his new city building game the ga

UVa 409 Excuses, Excuses! (字符串匹配)

409 - Excuses, Excuses! Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=96&page=show_problem&problem=350 Judge Ito is having a problem with people subpoenaed for jury duty giving rath

UVA之1330 - City Game

[题目] Bob is a strategy game programming specialist. In his new city building game the gaming environment is as follows: a city is built up by areas, in which there are streets, trees, factories and buildings. There is still some space in the area tha

UVA之11292 - Dragon of Loowater

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major problem. The shores of Rellau Creek in central Loowater had always been a prime breeding ground for geese. Due to the lack of predato

UVa 10602

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543 类型:贪心 原题: Company Macrohard has released it's new version of editor Nottoobad, which can understand a few voice commands.