小红的数组操作(hard version)

NC254289. 小红的数组操作(hard version)

描述

请注意，本题和easy版本的唯一区别是 $x$ 的数据范围没有了 $x=1$ 的限制。

小红拿到了一个数组，她可以进行若干次以下操作：

1.选择一个元素，花费 $p$ ，使其加 $x$ 。
1.选择一个元素，花费 $q$ ，使其减 $y$ 。

小红希望若干次操作后，数组的平均数是一个整数。你能帮小红求出最小的总代价吗？

输入描述

第一行输入五个正整数，代表数组的大小，其余几个变量如题目描述所示。
第二行输入个正整数，代表数组的元素。

输出描述

如果无解，请输出-1。
否则输出一个整数，代表最小的总代价。

示例1

输入:

3 3 1 5 6
2 3 4

输出:

示例2

输入:

5 5 2 4 3
2 3 2 2 2

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 203ms, 内存消耗: 460K, 提交时间: 2023-07-11 16:44:18

#include<iostream>
using namespace std;
long a,sum,n,p,x,q,y,cmin=4e12,i,j;
int main(){
	cin>>n>>p>>x>>q>>y;
	for(;i<n;i++) cin>>a,sum+=a;
	for(i=0;i<3495;i++)
		for(j=0;j<3495;j++)
			if((sum+i*x-j*y)%n==0)
				cmin=min(cmin,i*p+j*q);
	cout<<(cmin==4e12?-1:cmin);
	return 0;
}

上一题

下一题

详情