首页 > 其他分享 >烧烤 题解

烧烤 题解

时间:2024-08-07 16:05:33浏览次数:12  
标签:串烧 题解 烤肉 long 烧烤 钎子 长度 define

题目id:11063

题目描述

\(Snuke\)有一个烧烤聚会。
聚会上,他将制作\(N\)份串烧。
image
$\ \ \ \ \ \ \ $一份串烧
他有\(2N\)根烤肉钎子,它们都将用于制作串烧。第i个烤肉钎子的长度为Li。此外,他有无限供应的原料。他将原料串在两根烤肉钎子上做成一份串烧。一份串烧可串起的原料的最大数量取决于较短的那根烤肉钎子。
他怎么样串可以使得这\(N\)份串烧的原料数量总和最大?

解题思路

这题很像,最短的两根烤肉钎子肯定配对,次小的一对配对\(......\)最大的一对配对。
那么这题就很简单了,把烤肉钎子按长度从小到大排序,由于一份串烧可串起的原料的最大数量取决于较短的那根烤肉钎子这个条件,答案就是最小的烤肉钎子的长度\(+\)第\(3\)小的烤肉钎子的长度\(+......+\)第二大的烤肉钎子的长度,既\(i\)每次\(+2\),\(ans=\sum\limits_{i=1}^{2N}{a_i}\)。

AC Code

#include<bits/stdc++.h>
#define N 1000007
#define INF 1e18
#define MOD 998244353
#define LL long long
#define pb push_back
#define lb long double
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define IOS ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
LL n,a[N],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=2*n;++i)
        cin>>a[i];
    sort(a+1,a+2*n+1);
    for(LL i=1;i<=2*n;i+=2)
        ans+=a[i];
    cout<<ans;
    return 0;
}

标签:串烧,题解,烤肉,long,烧烤,钎子,长度,define
From: https://www.cnblogs.com/988176-/p/18347219

相关文章

  • 信创系统问题解决笔记
    本文记述解决信创系统显示问题过程经历,描述遇到的各种问题以及解决方法。问题描述测试反馈,在信创系统上,部分界面字体显示异常,表现为内容越界、文字区域显示为小空格,如下图所示:初步分析是字体原因,具体情况需要更进一步分析。问题复现测试团队的信创测试环境有UOS和Kylin两个......
  • CF1999题解
    题目链接CF1999A解题思路模拟。没了。参考代码/*Tips:你数组开小了吗?你MLE了吗?你觉得是贪心,是不是该想想dp?一个小时没调出来,是不是该考虑换题?打cf不要用umap!!!记住,rating是身外之物。该冲正解时冲正解!Problem:算法:思路:*/#include<bits/stdc++.h>usin......
  • 2024.8.7 模拟赛题解
    T1过于简单,不必阐述。T2给定一个仅包含\(A\)和\(P\)的字符串,每次操作可以删除相邻的\(AP\)或者\(PP\),问字符串最后的最小长度。$Sol:$为求最值问题,考虑贪心。先给出考场做法。发现若干的\(P\)是一定能合并掉的,于是贪心策略,就是如何最小化\(A\)的个数。对于每个......
  • 题解:Codeforces Round 964 (Div. 4) A
    A.A+BAgain?timelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputGivenatwo-digitpositiveinteger\(n\),findthesumofitsdigits.InputThefirstlinecontainsaninteger\(t\)(\(1......
  • 【题解】Solution Set - NOIP2024集训Day1 数据结构
    【题解】SolutionSet-NOIP2024集训Day1数据结构https://www.becoder.com.cn/contest/5429「CF1428F」FruitSequences线段树是可以维护区间最长子段的1。记固定右端点在\(i\),的答案为\(f_i\)。那么:\(a_i=0\),\(f_i=f_{i-1}\);\(a_i=1\),打一个单调栈维护所有的最长子......
  • 题解:P10543 [THUPC 2024 决赛] 黑白
    好题。题意\(n\timesm\)的网格图初始每个格子有黑有白,两人轮流操作,每次选择一个白格染黑。操作后不能存在一条\((1,1)\)到\((n,m)\)的路径,否则本次操作者输,另一人赢。思路首先判断是否一上来就输了。易发现到最后一定会操作到只剩一条道路,设路径长度为\(s\),那么\(s\)......
  • 题解:UVA11181 条件概率 Probability|Given
    主要思路:概率期望。首先可以发现\(n\)的数据极小。然后我们设\(a\)为为每个人买东西的情况,\(b\)为当有\(b\)个人去时的情况。大家都应该知道条件概率式子为\(P(a|b)=\frac{P(ab)}{P(b)}\)。然后暴力搜索\(P(ab)\)和\(P(b)\)。其实这道题有复杂度更低的dp做法,但......
  • 题解:CF1896G Pepe Racing
    主要思路:构造。思路方法一一个一个的找,分别查询\([1,n],[n+1,2n],\dots,[n(n-1)+1,n^{2}]\)中最快的人,再把\(n\)个人合起来查询,不过很明显的是,这个方法很蠢,并不能切掉此题。方法二找第二快的人,只有最快的人在的一组需重新询问,剩下答案无需改变。需排除的人的一组用不是现......
  • 2024牛客暑期多校训练营7 C Array Sorting 题解
    乱搞非正解写法。分类讨论各种情况。降序排序对应交换即可数组个数小直接考虑相邻的交换其他都看做随机数据考虑结合前面情况,很容易想到,先把数组变成一个尽量有序的数组(每个元素和自己正确的位置相差不大)。最后再多次相邻交换,使得每个元素都在正确位置。把数组变成......
  • 洛谷 P4910题解
    题目大意现在穿T次手串,每根手串的长度分别为不同的n,有木和金两种珠子,相邻两颗珠子必须有一个是金。题目思路分析我们现在设穿到第n个珠子时用金的方案数为f[1][n],用木的方案数为f[0][n]如果第n个珠子为金,那么前一颗珠子是什么都可以,因此f[1][n]=f[1][n-1]+f[0][n-1]而如果......