Ograda
【题目描述】
智慧有一个数列A，帆帆也有一个数列B,每个数列都有N个数字
对于一个数列，里面的数字都是不同的。
帆帆觉得智慧的数列比较好看，打算重排数列B，他想把自己的数列弄得尽量和智慧的数列相似，我们定义相似为B中相邻数字的大小关系和A中相邻数字的大小关系一致。
比如说A={a1,a2,a3}，其中a1<a2<a3.如果B={b1,b2,b3}要和A相似，必须满足b1<b2<b3.
不过帆帆想同时让自己的数列最好看，我们定义好看程度为|b1-b2|+|b2-b3|+....+|bn-1-bn|，帆帆希望好看程度尽量大。
PS.如果对题目还不理解请分析样例
帆帆因为要去和萌华领证（当然不是结婚证，是去台湾的签证），所以把这个问题交个了东东，但是东东很笨，他需要你的帮助。
【输入描述】
第一行：N(2<=N<=300 000)
第二行：智慧的数列
第三行：帆帆的N个数
【输出描述】
第一行：好看程度
第二行：重排后的帆帆的数列
【输入输出描述】
input
4
5 7 4 9
1 2 3 4
output
7
2 4 1 3
样例解释：
帆帆有以下几种重排的方法：
{1,3,2,4}好看程度:2+1+2=6
{1,4,2,3}好看程度:3+2+1=6
{2,3,1,4}好看程度:1+2+3=6
{2,4,1,3}好看程度:2+3+2=7
{3,4,1,2}好看程度:1+3+1=5
input
10
9 5 1 2 6 7 4 18 2012
10 40 20 30 50 7080 100 1000 500
output
3010
100 80 10 40 501000 20 70 500 30
【解法】
首先，暴力可以过部分点。但在社会主义建设的今天，一定要坚持AC的原则（我在讲什么）
然后想到，其实第一个数组有用的只是大小关系。于是可以定义对于a【i】和a【i+1】，只要确定大小关系。
于是样例一可以变成：<><
然后对b数组(第二个数列)快排,从左往右,依次在 < > 中间加入最大值,然后删去这个最大值(避免重复),在 > < 中间加入最小值,然后删去这个最小值,后面只需要在剩下的数组中找最大最小值(可以用两个指针l,r在数组中从两边往中间靠来实现)
接下来处理开头结尾,开头和结尾都放最大最小值(看开头和第二个,最后一个和倒数第二个的关系决定)
剩下的根据和下一个数的关系来从左往右填数,因为填什么不影响大小关系
证明:因为所填区域为单调 ,所以 |a-b|+|b-c|+....+|y-z|=a-z或z-a
所以可以直接填
【代码】
#include<cstdio> #include<cstdlib> #include<iostream> #include<iostream> #include<algorithm> #include<cmath> using namespace std; int a[300001]; int b[300001]; int c[300001]; int i,j,k,m,n,o,p,js,z,y; long long ll; int main() { FILE *fin,*fout; fin=fopen("ograda.in","rb"); fout=fopen("ograda.out","wb"); fscanf(fin,"%d",&n); for(int i=1;i<=n;i++)fscanf(fin,"%d",&a[i]); for(int i=1;i<=n;i++)fscanf(fin,"%d",&b[i]); sort(b+1, b+1+n); z=1; y=n; //====================================== for(i=2;i<n;i++) { if((a[i-1]>a[i])&&(a[i+1]>a[i])) { c[i]=b[z]; z++; } if((a[i-1]<a[i])&&(a[i+1]<a[i])) { c[i]=b[y]; y--; } } //======================================= if(a[1]<a[2]) { c[1]=b[z]; z++; } else { c[1]=b[y]; y--; } if(a[n]<a[n-1]) { c[n]=b[z]; z++; } else { c[n]=b[y]; y--; } //======================================= for(int i=2;i<=n-1;i++) { if(c[i]==0) { if(a[i]>a[i+1]) { c[i]=b[y]; y--; } if(a[i]<a[i+1]) { c[i]=b[z]; z++; } } } //======================================= for(int i=2;i<=n;i++)ll=ll+abs(c[i]-c[i-1]); fprintf(fout,"%I64d\n",ll); for(int i=1;i<=n;i++)fprintf(fout,"%d ",c[i]); fclose(fin); fclose(fout); }
