cf536c——思路题

题目

题目：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)$

代码

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 int n,a[maxn];

 int main()

 {

     scanf("%d", &n);

     for (int i = ; i < n; i++)  scanf("%d", &a[i]);

     sort(a, a + n);

     ll ans = ;

     for (int i = ; i < n / ; i++)

         ans += (ll) * (a[i] + a[n -  - i]) * (a[i] + a[n -  - i]);

     printf("%I64d\n", ans);

     return ;

 }

参考链接：https://codeforces.com/contest/1106/problem/C

巴特西

cf536c——思路题

题目

思路

代码

最新文章

热门文章