codeforces 158B Taxi(贪心)

悠悠 2022-05-16 02:12 126阅读 0赞

[题目链接][Link 1]

题目大意：有n组小学生想要搭乘出租车，每辆出租车最多能坐4个小学生，每组小学生必须坐同一辆出租车，问至少需要多少辆出租车？

分析：要想出租车的数量尽量少，那么肯定要尽量让能够拼车的组拼车，比如说3个人的组就可以找1个人的组拼车，2个人的组可以找2个人的组拼车，那么可以用贪心来解决，具体思路看代码注释。

#include<bits/stdc++.h>
    #define Clear(x) memset(x,0,sizeof(x))
    using namespace std;
    const int maxn = 1e2+7;
    int a[maxn];
    
    int main()
    {
        int n,num;
        while(~scanf("%d",&n))
        {
            Clear(a);
            int ans = 0;//车辆数
            for(int i=0;i<n;i++)
            {
                scanf("%d",&num);
                a[num]++;//记录这种人数的组有几组
            }
            while(n)//如果还有组
            {
                int now = 4;//每辆车能装4个人
                ans++;//车辆数+1
                for(int i=4;i>=1;i--)//贪心，从大到小装
                {
                    //用一个循while循环保证在能装下的情况下，不断装人
                    while(a[i]&&now>=i)//如果有人数为i的组，并且当前能装下这个组
                    {
                        a[i]--;//人数为i的组数-1
                        now-=i;//当前这辆车能的装人数-i
                        n--;//组数-1
                    }
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/158/B

发表评论取消回复

表情：

评论列表（有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #688 (Div. 2) B：Suffix Operations （差分，贪心）

原题链接：[B：Suffix Operations][B_Suffix Operations] 原题 ![b][] 题目大意给n个数，有两种操作，一是选定一个

一时失言乱红尘/ 2022年12月26日 14:26/ 0 赞/ 105 阅读

相关 codeforces C. Bits 贪心

C. Bits time limit per test 1 second memory limit per test 256 megabytes input sta

偏执的太偏执、/ 2022年07月24日 09:16/ 0 赞/ 185 阅读

相关 codeforces 276D 贪心

D. Little Girl and Maximum XOR time limit per test 2 seconds memory limit per test 2

妖狐艹你老母/ 2022年07月24日 06:26/ 0 赞/ 165 阅读

相关 CodeForces 873C(贪心)

问题描述: Ivan is playing a strange game. He has a matrix a with n rows and m columns. Eac

深藏阁楼爱情的钟/ 2022年06月07日 12:49/ 0 赞/ 126 阅读

相关 Codeforces 191B（贪心)

问题描述: In the capital city of Berland, Bertown, demonstrations are against the recent el

不念不忘少年蓝@/ 2022年06月07日 03:43/ 0 赞/ 204 阅读

相关 CodeForces 825D(贪心)

问题描述: You are given two strings s and t consisting of small Latin letters, string s can

ゝ一纸荒年。/ 2022年06月06日 14:16/ 0 赞/ 136 阅读

相关 CodeForces 825C(贪心)

问题描述: Makes solves problems on Decoforces and lots of other different online judges. Ea

r囧r小猫/ 2022年06月06日 13:00/ 0 赞/ 140 阅读

相关 codeforces 158B Taxi(贪心)

[题目链接][Link 1] 题目大意：有n组小学生想要搭乘出租车，每辆出租车最多能坐4个小学生，每组小学生必须坐同一辆出租车，问至少需要多少辆出租车？分析：要想出租车的

悠悠/ 2022年05月16日 02:12/ 0 赞/ 127 阅读

相关 codeforces1143B题解(贪心)

给出n，求1到n每个数字的每一位乘积的最大值 / Created by hao on 2019/4/14. 给出n，求1到n每个数字的每一位乘

╰半夏微凉°/ 2022年02月13日 01:41/ 0 赞/ 229 阅读

相关 Codeforces 353E 贪心

题意：给你一张有向图，第i条边连接i号点和(i + 1) % n号点，问最多可以选择多少个点，使得这些点互相不可达。思路：容易发现，如果某个边的集合点的数目大于等于2，那么

妖狐艹你老母/ 2021年12月12日 02:04/ 0 赞/ 225 阅读