P8927 「GMOI R1-T4」Rain

题目背景

求雨

玉皇爷爷也姓张，

为啥为难俺张*昌？

三天之内不下雨，

先扒龙皇庙，

再用大炮轰你娘。

如果再不下雨，张大帅就会轰掉全亚洲所有的宗教场所！

博丽神社因为可以在外界被看到，自然也无法幸免于难，灵梦十分着急，准备使用祖传秘法求雨……

题目描述

为了防止神社被“大炮开兮轰他娘”，灵梦需要求雨。

求雨需要在一条笔直的路上建 $n$ 个法阵，编号为 $1,2,\cdots ,n$。

给定一个长度为 $n$ 的数组 $a$，表示在 $a_1$ 到 $a_n$ 的位置建法阵，你要干的是给法阵编号。

灵梦需要来检测法阵效果，她会从 $1$ 号法阵走到 $2$ 号，从 $2$ 号再走到 $3$ 号，直到走到 $n$ 号，再从 $n$ 号走回 $1$ 号。

由于法阵的特殊效果，从 $i$ 个走到 $i+1$ 个的距离是 $\left|a_i\times p-a_{i+1}\times q\right|$。特别的，从 $n$ 号走回到 $1$ 号的距离是 $\left|a_n\times p-a_1\times q\right|$。$p,q$ 是给定的两个常数，$a_i,a_{i+1}$ 是两个法阵的位置。

灵梦希望你来求一下最大的行走距离，并输出对应法阵从 $1$ 号到 $n$ 号的位置排列。（多个只需输出一个即可）

输入格式

第一行一个整数 $n$，表示法阵数量。

第二行两个整数 $p,q$，表示法阵的倍率常量。

第三行 $n$ 个整数，表示数组 $a$。

输出格式

第一行一个整数，表示答案。

第二行 $n$ 个整数，表示对应位置 $a$ 的排列，按照编号从 $1$ 到 $n$ 输出。

输入输出样例 #1

输入 #1

10
2 3
1 2 3 4 5 6 7 8 9 10

输出 #1

131
5 6 7 1 8 2 9 3 10 4

说明/提示

本题开启 SPJ。

本题读入量较大，建议使用较快的读入方式。

对于 $100\%$ 的数据满足 $10\le n\le 10^6$，$1\le p,q\le 10^5$，$1\le a_i\le 10^5$。

编号	$n$	$p,q$	$a_i$	分数
$1$	$n=10$	$p,q\le 10^3$	$a_i\le 10^3$	$4$
$2$	$n=10$	$p,q\le 10^3$	$a_i\le 10^3$	$5$
$3$	$n=10$	$p,q\le 10^3$	$a_i\le 10^3$	$5$
$4\sim 6$	$n=19$	$p,q\le 10^5$	$a_i\le 10^5$	$10$
$7$	$n\le 10^4$	$p,q\le 10^5$	$a_i\le 10^5$	$8$
$8$	$n\le 10^4$	$p,q\le 10^5$	$a_i\le 10^5$	$9$
$9$	$n\le 10^4$	$p,q\le 10^5$	$a_i\le 10^5$	$9$
$10\sim 12$	$n\le 10^6$	$p,q\le 10^5$	$a_i\le 10^5$	$10$

C++实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
const int N=1e6+5,V=1e5+5;
int n,p,q,a[N],ans[N],m,p1[N],cnt1,p2[N],cnt2,sum;
bool pa[N],qa[N];
struct node{
	int val,pos;
	bool operator<(const node &p)const{return val<p.val;}
}tmp[N<<1];
signed main(){
	n=read(),p=read(),q=read();
	for(int i=1;i<=n;++i)a[i]=read(),tmp[(i<<1)-1]=(node){p*a[i],i},tmp[i<<1]=(node){q*a[i],i};
	sort(tmp+1,tmp+(n<<1)+1);
	for(int i=1;i<=n;++i)sum-=tmp[i].val;
	for(int i=n+1;i<=(n<<1);++i){
		if(tmp[i].val==p*a[tmp[i].pos])pa[tmp[i].pos]=1;
		else qa[tmp[i].pos]=1;
		sum+=tmp[i].val;
	}
	for(int i=1;i<=n;++i){
		if(pa[i]^qa[i])ans[++m]=i;
		else if(pa[i]&&qa[i])p2[++cnt2]=i;
		else p1[++cnt1]=i;
	}
	for(int i=1;i<=cnt1;++i){
		if(p<=q)ans[++m]=p2[i],ans[++m]=p1[i];
		else ans[++m]=p1[i],ans[++m]=p2[i];
	}
	printf("%lld\n",sum);
	for(int i=1;i<=m;++i)print(a[ans[i]]),putchar(' ');
	return 0;
}

后续

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