首页 > 其他分享 >Cf 730J Bottles

Cf 730J Bottles

时间:2022-12-25 22:45:42浏览次数:50  
标签:Bottles int sum Cf 瓶子 re2 最少 730J

Cf 730J Bottles

题意:

一共有n个瓶子,给出每个瓶子当前的水量和当前的容量。

将一瓶水中1ml水转移到别的瓶子上需要1s

求在使用最少瓶子数的前提下,转移需要的时间最少。

数据范围:

思路:

贪心+dp

可以贪心得到,最少需要使用的瓶子数量

然后现在已知最少瓶子数量,求需要转移的最少时间。

贪心的想,在瓶子数量一定的时候,我们肯定想这些瓶子里面的装的水尽可能多,因为水总数量是一定的,不是原有瓶子的水都需要花费1个单位时间。

然后我们选择出瓶子的时候,还需要确保瓶子的容量,所以状态有以下定义

实现:

#include <stdio.h>
#include <algorithm>
#define int long long
using namespace std;
const int N = 105;
int a[N], b[N];
int f[N][N * N]; //当前使用i个瓶子,这i个瓶子的容量为j,这些瓶子里面最多有f[i][j]ml的水
signed main()
{
    int n;
    scanf("%lld", &n);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N * N; j++)
            f[i][j] = -1e18;

    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j; j--)
            for (int k = b[i]; k < N * N; k++)
                f[j][k] = max(f[j][k], f[j - 1][k - b[i]] + a[i]);
    int re1 = 0, tot = 0;
    sort(b + 1, b + 1 + n);
    for (int i = n; i >= 0; i--)
    {
        re1++,
            tot += b[i];
        if (tot >= sum)
            break;
    }
    int re2 = 0;
    for (int i = sum; i < N * N; i++)
        re2 = max(re2, f[re1][i]);

    printf("%lld %lld\n", re1, sum - re2);
    return 0;
}

标签:Bottles,int,sum,Cf,瓶子,re2,最少,730J
From: https://www.cnblogs.com/zxr000/p/17004791.html

相关文章

  • Cf 54C First Digit Law
    Cf54CFirstDigitLaw题意:一个数组中有n个数,给出第\(i\)个数的范围\([l_i,r_i]\),定义这n个数中以1开头的数为特殊数,求这n个数中,特殊的数出现的比例至少为k%的概率......
  • Cf 429B [Working out]
    Cf429BWorkingout题意:给定一个n行m列的矩阵A,在该矩阵中找出两条路径,要求:第一条路径从矩阵左上角(1,1)走到矩阵右下角(n,m),每次只能向下或向右走。第二......
  • Cf 455A [Boredom]
    Cf455ABoredom题意:给出\(n\)个数字,从中选一个\(a_k\)删除,\(a_k\)为你获得的值,删除\(a_k\)后,如果数组里面有\(a_{k+1},a_{k-1}\)也会被删除,求获得值最大为......
  • Cf1625C Road Optimization
    Cf1625CRoadOptimization题意:在一条长为\(1\)的公路上有\(n\)个路标,第\(i\)个路标在第\(d_i\)米处,限速\(a_i\),意味着在这个路标到下一个路标之间的路段最快......
  • 【推荐系统算法实战】协同过滤 CF 算法(Collaborative Filtering)
    什么是协同过滤算法?协同过滤推荐(CollaborativeFilteringRecommendation)。仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。学术界对协同过滤算法进行了深......
  • CF732D Exams 题解
    题目链接题目分析:首先可以发现,如果当前第\(i\)天可以完成所有考试,那么第\(i+1\)天一定也可以。因此,答案具有单调性。考虑二分,将原问题转换为判定性问题。判定是否......
  • CF--795--E
    E.NumberofGroups关键感觉是一个很神奇的合并的方法。首先对这个区间进行左右拆点,然后进行排序处理。如果加进来的这个点是左端点,那就把在区间里面的左端点进行合并......
  • CF864C Bus 题解
    题目传送门题目大意一辆汽车从\(0\)到\(a\)往返\(k\div2\)次(也就是去算一次,回算一次);原来有\(b\)升油,每行驶一单位距离消耗一升油,在\(f\)有加油站(可以加满油......
  • CF1735A Working Week 题解
    题目传送门题目大意一周有\(n\)天,有三天休息日,其中第\(n\)天一定休息。现需要安排剩下的两个休息日,要求:不能使得休息日相邻。这两个休息日将\(n-1\)天分成三......
  • cf1763 —F. Edge Queries
    F.EdgeQuerieshttps://codeforces.ml/contest/1763/problem/F题意n个点m条边的无向图,保证一个点不会存在多个连通分量中,q次询问,问对于从u到v的所有路径上的边,删掉一条......