算法总结--数学{ ∑ 公式}

feizhu_QWQ · 2024-07-25 13:51:34 · 个人记录

(｡･∀･)ﾉﾞ嗨飞竹小课堂第16课开课喽!
咳咳，今天我们又讲数学~
(全是偏蓝的题目
排名
这这这，太难了吧！
这道题题意有点复杂，飞竹慢慢解释
每个a_i都有对应的f_i和g_i，
这道题让我们满足每一个a_i的f_i <= k <= g_i

我们就需要从后面的数中选择较大的几个数变为a_i 因为我们可以得知，要满足要求，就要改变f_i和g_i，我们只需用把一些没到a_i的数变为a_i，使得g_i更大，这样就可以满足要求，懂？

那么代价就是：(k - i)* s_i . x - sum_k - sum_i
如果为了计算后面的数达到a_i差多少，很可能花费O(n)的时间复杂度，所以此处用前缀和优化，懂？

• i==k

这要想吗？什么都不会发生，因为a_k本身就满足要求，答案+0

• i > k

  我们就需要把比a_i小的数拉到a_i代价就是a_k - a_i了~ 最终代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c,n,k,sum[1000005],ans[1000005];
struct node
{
    int x,id;
}s[1000005];
bool cmp(node q,node h)
{
    return q.x>h.x;
}
signed main()
{
    cin>>c>>n>>k;
    for(int i=1;i<=n;i++) cin>>s[i].x,s[i].id=i;
    sort(s+1,s+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+s[i].x;
    }
    for(int i=1;i<k;i++)
    {
        ans[s[i].id]=(k-i)*s[i].x-(sum[k]-sum[i+1-1]);
    }
    for(int i=k;i<=n;i++)
    {
        ans[s[i].id]=s[k].x-s[i].x;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

这道题很恨很难
这道题有两大大大大大大大难点：

1. 公式
2. 模mod

这道题的贪心思想就是把复数放在第一段或最后一段，把整数全部放在最后一段，中间全是空段，就可以使答案最大
可这道题的时间复杂度够不了一点，难受~
那么我们就把这个过程推公式，开始！
假设t为负数分界线：

\= \sum_{i=1}^{t}(a_i ^2+2a_i +1) +\sum_{t+1}^{n}(a_i^2 +2m a_i + m^2)

\= (\sum_{i=1}^{t} (a_i^2)+2\sum_{i=1}^{t}a_i + t )+(\sum_{t+1}^{n})(a_i)^2+2m(\sum_{t+1}^{n})a_i)+m^2×(n-t)

\=\sum_{i=1}^{t}(a_i^2)\sum_{i=1}^{t}(a_i^2+2a_i+t)+(\sum_{t+1}^{n}(a_i^2)+2m+\sum_{t+1}^{n}a_i+m^2×(n-t)

\=\sum_{i=1}^{n} (a_i^2)+2\sum_{i=1}^{t}a_i+2m\sum_{t+1}^{n}a_i+t+m^2*(n-t)
接下来进行前缀和优化：

终终终终于写完了，(2000字小作文

对了，因为a是单调不见的，所以我们找t的时候只会不断向左移，时间是O(1)的哦！

接着，我们将mod
这道题的加减乘都要mod，mod套mod很麻烦，于是我们把需要mod的算式写成一个函数，这个是mod公式：
加法：

减法：

乘法：

我们把他们放进函数里就可以啦！
终于讲完这道题了，什么？绿题？
家人们，轰炸讨论区，必须升蓝！！！

ヾ(￣▽￣)Bye~Bye~