【贪心+推式子计算贡献】ABC216 E

妖狐艹你老母 2024-03-17 16:02 59阅读 0赞

[E - Amusement Park (atcoder.jp)][E - Amusement Park _atcoder.jp]

题意：

![578018ad8dee4207ad32bf02dcb0e32d.png][]

思路：

首先，优先访问ai大的贡献一定大

因此可以考虑把ai从小到大排个序，然后从尾部遍历

![format_png][]

然后去计算贡献

贡献比较难推，但是手搓一下还是可以推出来的

先想出几何模型，再去手推

如果不会几何模型，直接去手推找规律也可

![e29ca8e7a0ab4b5fbc8870de90d91cdf.png][]

![9736b6083ff748f390f08374d1687ff3.jpeg][]

![5c488f13e93d43c4a0f996cbf153e7f3.jpeg][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int a[100005];
    signed main()
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        long long ans=0;
        for(int i=n;i>=1;i--)
        {
            int num = n-i+1;
            int cost = num*(a[i]-a[i-1]);
            if(cost<=k)
            {
                k-=cost;
                ans+=num * (a[i]+a[i-1]+1) * (a[i]-a[i-1]) / 2;
            }
            else
            {
                int t1 = k/num;
                int t2 = k%num;
                ans += num * (a[i] + a[i]-t1+1) * t1 / 2;
                ans += (a[i]-t1)*t2;
                break;
            }
        }
        printf("%lld\n",ans);
    }

[E - Amusement Park _atcoder.jp]: https://atcoder.jp/contests/abc216/tasks/abc216_e
[578018ad8dee4207ad32bf02dcb0e32d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1e6e8cb1023a4912bde6795eebd62188.png
[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/330a58c90c8749c4a787f3c54de309f3.png
[e29ca8e7a0ab4b5fbc8870de90d91cdf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b7a61067fd8d4dd389f896db4364299e.png
[9736b6083ff748f390f08374d1687ff3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4bae04f923c042679cc328d5273b209f.png
[5c488f13e93d43c4a0f996cbf153e7f3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f821a14b2c174e7abcef771d4cb0212d.png