1. Johngo学长首页
  2. 技术点详细复盘专题
  3. 数据结构和算法

CF1467C Three Bags

• 数据结构和算法 • 阅读 120

传送门

CF1467C Three Bags

思路：对于一般情况，我们有三个袋子，容易想到把袋子里物品的价值排序。然后贪心，我们想让最后的价值最大，则三个袋子最后都可以剩余一个物品，这三个物品总和需要最大，最好的情况就是三个物品的符号”+”，”-“，”-“,这样总价值直接可以算是每个袋子中物品绝对值的累加和。为了让三个物品价值最大，我们可以容易想到，价值大的物品减去价值小的物品，让可用价值尽可能大，而且最后剩余每个袋子的最后物品符号分别是”+””-“”-“。这样，我们之前每个袋子的物品都排好了序，容易想到，对于三个袋子中，每个袋子价值最小的物品是关键。因为我们需要让可用价值尽可能大，所以我们可以让三个袋子中，最小值最大的那个物品为”+”,然后让其他两个袋子中的最小物品收集其他价值，这样就满足了三个袋子都只剩下一个物品且满足”+””-“”-“。我们可以让最小值最大和最小值中间大的袋子中其他物品累加减去和最小值最小的物品让其为”-“，然后让最小值最小的其他物品累加和减去最小值中间大的那个物品让其为”-“就可以了。但最小值最小的其他所有物品和最小值中间大的物品的差值会有特殊情况，例如：最小值的其他物品 1，1；中间值的最小值 4.这样（4-1-1 = 2）,这里需要特判一下，我们发现两者的差值只需要取一个abs就可以了，上面的例子可以转化为：1 – 中间值放入最小值的袋中，变成了abs（-3+1）。

然后就是特殊情况，即三个袋子中任意一个袋子的物品只有一个的情况，需要特殊判断。

CF1467C Three Bags 
 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #define LL long long
12 #define lson(rt) (rt << 1)
13 #define rson(rt) (rt << 1 | 1)
14 using namespace std;
15
16 const int N = 1e3 + 10;
17 struct node
18 {
19     int v, id;
20
21     bool friend operatorconst node& a, const node& b)
22     {
23         return a.v < b.v;
24     }
25 };
26 int a[N];
27
28 void solve ()
29 {
30     int n, m, k, x;
31     scanf("%d%d%d", &n, &m, &k);
32     vector<int > a[3];
33     for(int i = 0; i < n; ++i) {
34
35         scanf("%d", &x);
36         a[0].push_back(x);
37     }
38     for(int i = 0; i < m; ++i) {
39         scanf("%d", &x);
40         a[1].push_back(x);
41     }
42     for(int i = 0; i < k; ++i) {
43         scanf("%d", &x);
44         a[2].push_back(x);
45     }
46     for(int i = 0; i < 3; ++i) sort(a[i].begin(), a[i].end());
47
48     vector vn;
49     vn.push_back({a[0][0], 0});
50     vn.push_back({a[1][0], 1});
51     vn.push_back({a[2][0], 2});
52
53     sort(vn.begin(), vn.end());
54
55
56     int maxx = vn[2].id;
57     int midd = vn[1].id;
58     int minn = vn[0].id;
59
60     long long maxv, midv, minv;
61     maxv = midv = minv = 0;
62     for(auto x : a[maxx]) maxv += x;
63     for(auto x : a[midd]) midv += x;
64     for(auto x : a[minn]) minv += x;
65   //  printf("(%lld %lld %lld)\n", maxv, midv,minv);
66     midv -= a[midd][0];
67     minv -= a[minn][0];
68     maxv -= a[maxx][0];
69  //   printf("(%lld %lld %lld)\n", maxv, midv,minv);
70    // printf("(%d %d %d)\n", a[maxx].size(), a[midd].size(), a[minn].size());
71     long long ans = 0;
72     if(a[minn].size() == 1) {
73         ans += maxv + midv + a[maxx][0] + a[midd][0] - a[minn][0];
74     } else if(a[midd].size() == 1) {
75    //     cout << "s" << endl;
76         ans += abs(minv + a[minn][0] - a[midd][0]);
77         ans += a[maxx][0] + maxv;
78     } else if(a[maxx].size() == 1 && a[maxx][0] < a[midd][0] + a[minn][0]) {
79         ans += midv + minv + a[midd][0] + a[minn][0] - a[maxx][0];
80     } else {
81    //     cout << "s" << endl;
82         ans += a[maxx][0] + maxv + midv - a[minn][0];
83         ans += abs(minv - a[midd][0]);
84     }
85
86     printf("%lld\n", ans);
87 }
88
89 int main ()
90 {
91
92     solve();
93
94     return 0;
95 }

Original: https://www.cnblogs.com/SSummerZzz/p/14253958.html
Author: SummerMingQAQ
Title: CF1467C Three Bags

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584281/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

  • cc++实现天气数据获取

    #include <iostream> #include <winsock2.h> #pragma comment(lib, "ws2_32.li…

    数据结构和算法 2023年6月7日
    081

  • Java I/O流 复制文件速度对比

    Java I/O流 复制文件速度对比 首先来说明如何使用Java的IO流实现文件的复制： 第一步肯定是要 获取文件 这里使用字节流，一会我们会对视频进行复制（视频为非文本文件，故使…

    数据结构和算法 2023年6月7日
    0132

  • 977.有序数组的平方

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 示例 1： 输入：nums = [-4,-1,0,3,10]输出…

    数据结构和算法 2023年6月8日
    080

  • kivy入门之布局(五)

    创建多页面布局 1 from kivy.app import App 2 from kivy.uix.button import Button 3 from kivy.uix.pa…

    数据结构和算法 2023年6月12日
    094

  • 线索二叉树的构造及前驱后继的查找

    在本文中，我将介绍三种线索二叉树的构造方法，包括中序线索二叉树、先序线索二叉树以及后序线索二叉树。在介绍过程中，首先我会给出构造的基本思路，然后说明其中几点注意事项，最后我将给出代…

    数据结构和算法 2023年6月12日
    097

  • 【典】名言

    博客园 ：当前访问的博文已被密码保护 请输入阅读密码: Original: https://www.cnblogs.com/yolanda-yxr/p/16744804.htmlA…

    数据结构和算法 2023年6月7日
    089

  • [LC1260]二维网格迁移

    二维网格迁移 题目描述 给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。每次「迁移」操作将会引发下述活动：位于 grid[i][j]…

    数据结构和算法 2023年6月8日
    093

  • 集合幂级数相关

    CHANGE LOG NOI 大纲里没有把位运算卷积如 FMT，FWT，子集卷积等知识点单独列出，但高维前缀和（SOSDP）是应用比较广泛的重要算法。 学习上述算法，首先要理解什么…

    数据结构和算法 2023年6月12日
    0107

  • 设计模式之代理模式

    代理模式英文名叫 Proxy Pattern 看下Proxy的含义 [ˈprɑ:ksi] n.代表权；代理人，代替物；委托书； 主要表达的就是代表、代替、委托的意思。 我对这个模式…

    数据结构和算法 2023年6月8日
    094

  • [总结]2022/1/20

    P1心路历程 开题12min看完题目，认为T2、T4是大模拟，T1是一个dp之类的东西，T3看到想到了宽搜。认为T2好做一点，于是开始干T2。认为自己的想法是对的，写了一个跑不满 …

    数据结构和算法 2023年6月8日
    090

  • epoll服务器开发一

    socket英文单词为插座的意思，在网络通信中代表套接字，取插座的意思代表socket需要像插头插座一样配套使用，所以socket需要指定具体的五元组才可以通信，包括源ip、源端口…

    数据结构和算法 2023年6月16日
    094

  • C++ sort() 用法介绍

    std:: sort() 所属头文件 介绍 可以对某个范围进行排序 不保证等效元素保持其原始相对顺序 参数 first, last 代表需要排序内容的开始位置和结尾，范围是 [fi…

    数据结构和算法 2023年6月8日
    070

  • 区间dp

    一.什么是区间dp? 顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 二.核心思路 既然让…

    数据结构和算法 2023年6月7日
    077

  • Linux下Redis的安装

    配置⽂件⽬录为/usr/local/redis/redis.conf sudo cp /usr/local/redis/redis.conf /etc/redis/ Origina…

    数据结构和算法 2023年6月7日
    091

  • 算法： 求1+2+…+n

    问题 求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 解决 //不能使用乘除…

    数据结构和算法 2023年6月12日
    082

  • 字符串匹配

    一、BF算法 Brute-Force简称BF算法，也称单匹配算法。采用穷举的思路。BF是暴力的意思。 算法思路： 从T的每一个字符开始依次与P的字符进行匹配。 BF算法匹配过程： …

    数据结构和算法 2023年6月7日
    079
亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球