cf536c——思路题

阳光穿透心脏的1/2处 2023-08-17 15:47 119阅读 0赞

## 题目 ##

题目：[Lunar New Year and Number Division][]

题目大意：给定一个数字序列，可以任意分组（可调整顺序），但每组至少两个，求每组内数字和的平方的最小值

## 思路 ##

首先，易证两两分组是最好的。

其次，我们假设将序列$\{a\_i\}$分成序列$\{b\_i\}$和$\{c\_i\}$,所以

$$sum=\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{n\}(b\_i+c\_i)^2$$

我们不关心这部分（因为不管怎么划分，这部分值都不会变）：

$$\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{n\}(b\_i^2+c\_i^2)$$

我们仅需考虑$\\sum\_\{i=1\}^\{n\}b\_ic\_i$的最小值，由Rearrangement Inequality（排序原理）知，我们须将大者与小者两两结合。

时间复杂度：$\\mathcal\{O\}(n \\log n)$

## 代码 ##

1 #include<cstdio>
     2 #include<cstring>
     3 #include<algorithm>
     4 using namespace std;
     5 
     6 typedef long long ll;
     7 const int maxn = 300000 + 10;
     8 int n,a[maxn];
     9 
    10 
    11 int main()
    12 {
    13     scanf("%d", &n);
    14     for (int i = 0; i < n; i++)  scanf("%d", &a[i]);
    15     sort(a, a + n);
    16     ll ans = 0;
    17     for (int i = 0; i < n / 2; i++)
    18         ans += (ll)1 * (a[i] + a[n - 1 - i]) * (a[i] + a[n - 1 - i]);
    19     printf("%I64d\n", ans);
    20     return 0;
    21 }

参考链接：[https://codeforces.com/contest/1106/problem/C][Lunar New Year and Number Division]

转载于:https://www.cnblogs.com/lfri/p/10346129.html

[Lunar New Year and Number Division]: https://codeforces.com/contest/1106/problem/C

发表评论取消回复

表情：

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

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

相关阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 93 阅读

相关 CF1197C

CF1197C 题意： > 有一个递增的数列，把它分成k段，找到这样的分段方法，即每段最大值减最小值的和最小解法： > 分成k段，即要加k-1个隔...

太过爱你忘了你带给我的痛/ 2024年04月20日 10:28/ 0 赞/ 94 阅读

相关 CF280C

CF280C > ZR补题计划题意： > 一棵有根树，每次选择一个未删除的节点，然后删除它和它的子树内的点，问期望删多少次可以把整个树删完解析： ...

刺骨的言语ヽ痛彻心扉/ 2024年04月20日 10:26/ 0 赞/ 77 阅读

相关 CF985C

CF985C 题意： > 你要组成N个木桶，组成每个木桶需要K个木块，（第二行给你N\*K个木块），使得任意两个木桶之间的差值不超过L的情况，使得所有木桶可...

客官°小女子只卖身不卖艺/ 2024年04月20日 10:26/ 0 赞/ 87 阅读

相关 cf536d——优先队列的运用

题目题目： Lunar New Year and a Wander 题目大意：给定一个n个顶点（编号1~n）、m条边的图，求从顶点1出发的字典序最小的路径（途径的边可

喜欢ヅ旅行/ 2023年08月17日 15:47/ 0 赞/ 117 阅读

相关 cf536c——思路题

题目题目：[Lunar New Year and Number Division][] 题目大意：给定一个数字序列，可以任意分组（可调整顺序），但每组至少两个，求每组

阳光穿透心脏的1/2处/ 2023年08月17日 15:47/ 0 赞/ 120 阅读

相关 cf536b——优先队列的运用

题目题目：[cf536 B题][cf536 B] 题目大意：一个饭店有n种食物，每种食物有对应的价格和数量，然后有m个顾客，每个顾客需要$d\_j$份第$t\_j$种

淩亂°似流年/ 2023年08月17日 15:47/ 0 赞/ 132 阅读

相关 cf交互题

[链接][Link 1] include <iostream> include <algorithm> using namespace std;

忘是亡心i/ 2022年09月09日 06:54/ 0 赞/ 157 阅读

相关线性dp——cf1012C好题

比较套路的dp题 / dp[i][j][0|1]:前i座山盖了j座房子，第i座不盖|盖 dp[i][j][0]=min( dp[i-1][j][0]

骑猪看日落/ 2021年12月01日 16:46/ 0 赞/ 249 阅读

相关 cf 1179 C

目录 A B C A 模拟出A不是最大值的情况，存起来。最多有n个。当A为最大值的时候，后面n-1个数开始循环。查询分两种情况讨论就行了

比眉伴天荒/ 2021年11月01日 10:20/ 0 赞/ 286 阅读