【ACGO巅峰赛#19】T2打印机 题解

简单模拟题。

由于题目中说要么双面打印要么单面打印，所以我们可以同时模拟这两个情况求出解后，再取两者的最小值为答案。

对于单面打印很简单，只需要使用 $m$ 次双面打印，剩下 $n-m$ 页全部单面打印即可。价格 $am+c(n-m).$

对于双面打印，则必定是 $\{1,2\},\{3,4\},...,\{2k-1,2k\}$ 的形式打印，而每个二元组里只要有一个需要彩色，那么就必须用一次彩色双面。因此我们只要统计含有至少一个彩色的二元组数量，可以用map实现。

两个数 $n,m$ 位于同一个二元组，当且仅当 $(n+1)//2 = (m+1)//2.$

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e6+10;
int n,m,a[N];
int c1,c2,c3,c4;
map<int,int> ma;

signed main(){
	ios::sync_with_stdio(false);
	cin>>c1>>c2>>c3>>c4;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		ma[(a[i]+1)/2] = 1;
	}
	int cnt = 0;
	for(auto it:ma) cnt++;
	int ans = min(c3*(n-m)+c1*m,c4*((n+1)/2-cnt)+c2*cnt);
	cout<<ans;
	
	return 0;
}