P10412 「QFOI R2」钟声远带斜阳

题目描述

注意：本题中的所有数列下标从 $0$ 开始。

小 R 是一个可爱的女孩子，她喜欢研究无穷数列。

她称一个无穷数列 $b$ 是美妙的，当且仅当存在自然数 $k_0$，使得对于所有 $k\ge k_0$，都满足 $b$ 中下标在区间 $[k_0,k]$ 内的所有数的和非负（即 ${\sum }_{i=k_0}^k{b}_i\ge 0$）。例如，数列 ${\alpha }_i=i-5$ 是美妙的，取 $k_0=5$ 符合要求；但 ${\beta }_i=-i$ 不是美妙的。

她目前只有一个长度为 $n$ 的有穷数列 $a$，可以进行任意次以下三种操作：

1. 花费 $p$ 的代价，选择一个整数 $i$（$0\le i<n$），将 $a_i$ 增加一。
2. 花费 $q$ 的代价，选择一个整数 $i$（$0\le i<n$），将 $a_i$ 删除，同时更新 $n$ 为新的数列长度。不能将数列删空。
3. 花费 $r$ 的代价，选择两个整数 $i,j$（$0\le i<j<n$），交换 $a_i$ 与 $a_j$。

她希望在若干次操作后，用无限个有穷数列 $a$ 依次相接得到无穷数列 $b$（即 $b_i=a_{i\mathrm{mod}n}$），使得 $b$ 是美妙的。请你求出最小的代价。

输入格式

第一行四个整数 $n,p,q,r$。

第二行 $n$ 个整数，表示数列 $a$。

输出格式

一行，一个整数，表示最小代价。

输入输出样例 #1

输入 #1

5 1 2 5
2 -2 3 -3 -1

输出 #1

1

输入输出样例 #2

输入 #2

5 2 1 5
2 -2 3 -3 -1

输出 #2

1

输入输出样例 #3

输入 #3

5 1 1 1
0 1 2 3 4

输出 #3

0

说明/提示

样例 $1$ 解释

花费 $p=1$ 的代价将 $a_3$ 增加一，得到数列 $b=[2,-2,3,-2,-1,2,-2,3,-2,-1,\cdots ]$ 是美妙的，取 $k_0=2$ 符合要求。

可以证明不存在代价更小的方案。

---

样例 $2$ 解释

花费 $q=1$ 的代价将 $a_1$ 删除，得到数列 $b=[2,3,-3,-1,2,3,-3,-1,\cdots ]$ 是美妙的，取 $k_0=0$ 符合要求。

可以证明不存在代价更小的方案。

---

数据范围

本题采用捆绑测试。只有通过子任务中所有测试点以及所有依赖的子任务，才能获得相应的分数。

对于全部数据：$1\le n\le 10^5$，$1\le p,q,r\le 10^9$，$|a_i|\le 10^9$。

• 子任务一（$10$ 分）：$n=1$。
• 子任务二（$10$ 分）：$n\le 10$。依赖子任务一。
• 子任务三（$20$ 分）：$|a_i|\le 1$。
• 子任务四（$20$ 分）：$\sum |a_i|\le 10^5$。依赖子任务三。
• 子任务五（$40$ 分）：无特殊限制。依赖子任务一、二、三、四。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
long long n,p,q,r,sum,ans,a[N];//要开 long long 
bool f=true;//判断之前有没有用过修改操作 
int main()
{
	cin>>n>>p>>q>>r;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	if (sum>=0)
	{
		cout<<0<<endl;
		return 0;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++)
	{
		long long t=min(-sum,-a[i]);
		if (q<t*p)//如果删除操作更优 
		{
			ans+=q;
			sum+=t;
		}
		else//如果修改操作更优 
		{
			ans+=t*p;
			sum+=t;
			f=false;
		}
		if (sum>=0)
			break;
	}
	if (a[n]<0)//不能删空 
	{
		if (f)//如果之前都是删除操作，说明 a数组中只有啊 a[n]这一个数 
			ans+=(-a[n])*p;
		else
			ans+=min(q,(-a[n]*p));
	}
	cout<<ans<<endl;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容