cf1165 Round #560 Div3-E【贪心】

Date：2022.01.05

题意：给定a、b数组，a数组不能变位置，b可变位置，求变化位置后要求式子的最小和。特别注意不是取模最小的和！！！！！

思路：找规律，第i项即为a[i]$\ast$b[i]，我们发现第i项要乘i $\ast$ (n-i+1)次，我们要让总和最小，因此每一项都要尽可能小，因此每一项都是一个大数 $\ast$ 一个小数。因为a不能动，因此a对答案的贡献是不变的，恒为a[i] $\ast$ i $\ast$ (n-i+1)【下标i从1开始】。所以只需要将a[i] $\ast$ i $\ast$ (n-i+1)从小到大排序，同时乘上从大到小排序后的b[i]，再累加即为贪心解。除此之外，记得排序a[i] $\ast$ i $\ast$ (n-i+1)和b[i]前都不要取模！！！！！否则得到的就是和取模后最小的解，而不是和自身最小的！！！！！
代码如下：

#include 
#include 
#include 
using namespace std;
const int N = 2e5+10,mod=998244353;
typedef unsigned long long LL;
LL a[N],b[N],t,n,m;
bool cmp(LL a,LL b)
{return a>b;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++) {cin>>a[i];a[i]=a[i]*(LL)(i+1)*(n-i);}for(int i=0;i<n;i++) cin>>b[i];sort(a,a+n);sort(b,b+n,cmp);LL res=0;for(int i=0;i<n;i++) res=(res+a[i]%mod*b[i]%mod)%mod;cout<<res;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！