# Noble 的博客

♡虹蓝♡

### 题解 【卢卡杨比火车站/（Nescafé杯模拟赛一）星之船】

posted on 2019-07-10 20:44:53 | under 未分类 |

#### 数据范围

/*

*/
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int kmaxn=300+15;
ll dwlx[kmaxn];//达瓦里希
ll glg[kmaxn];//古拉格
ll Len;
ll ans;
ll anss;
int n,m;
struct Status{
int pr;
int dir;//0 left   1 right or direct//门在人的左/右侧
};
enum DIRECTION{
L,R
};
Status st[kmaxn];
priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q;//所需s值，前进至下一个状态的同志的编号。
ll myabs(ll l)
{
return l>0?l:-l;
}
int lb(ll v)
{
return lower_bound(glg+1,glg+n+1,v)-glg;
}
{
ll d=glg[st[p].pr];
return myabs(dwlx[p]-d)+1;
}
{
if(st[p].pr<=1)return Len-glg[n]+1;
ll x=dwlx[p];
ll a=glg[st[p].pr-1];
ll b=glg[st[p].pr];
return (2*x-a-b+1)/2;
}
{
if(st[p].dir==L)
else
}
ll cal_num,cal_mul;//常数项，s的系数
{
ll d=glg[st[p].pr];//这个d考试时候是int，然后就爆了
if(st[p].dir==L)//dir change
{
cal_num+=d;
cal_num-=dwlx[p];
cal_mul++;
st[p].dir=R;
cal_num+=d;
cal_num-=dwlx[p];
cal_mul++;
}
else//pair change
{
st[p].dir=L;
cal_num-=d;
cal_num+=dwlx[p];
cal_mul--;
d=glg[--st[p].pr];
cal_num-=d;
cal_num+=dwlx[p];
cal_mul--;
}
q.push(make_pair(t,p));
}
int main()
{
ios::sync_with_stdio(false);
cin>>Len>>m;
Len*=10;
for(int i=1;i<=m;++i)
{
cin>>dwlx[i];
dwlx[i]*=10;
}
cin>>n;
for(int i=2;i<=n;++i)
{
cin>>glg[i];
glg[i]*=10;
}
ll t1,t2;
int p;
for(int i=1;i<=m;++i)//求初始配对
{
t1=t2=Len*m;
p=lb(dwlx[i]);
if(p<=n)//right or direct
t1=myabs(glg[p]-dwlx[i]);
--p;
if(p>0)//left
t2=myabs(glg[p]-dwlx[i]);
if(t1<t2)//dwlx glg
{
st[i].dir=R;
st[i].pr=p+1;
cal_num+=glg[p+1];
cal_mul++;
cal_num-=dwlx[i];
}
else//glg dwlx
{
st[i].dir=L;
st[i].pr=p;
cal_num-=glg[p];
cal_mul--;
cal_num+=dwlx[i];
}
}
for(int i=1;i<=n;++i)//求每个点状态前进所需的s.
{
q.push(make_pair(t1,i));
}
////初始状态答案
ans=0;
t1=0;
t2=q.top().first-1;
ll tans,nows;
if(cal_mul>0)
nows=t2-1;
else
nows=t1;
tans=cal_mul*nows+cal_num;
if(tans>ans){
ans=tans;
anss=nows;
}
while((t1=q.top().first)<=Len-glg[n])//range [t1,t2]
{
p=q.top().second;
q.pop();
while((t2=q.top().first)==t1)//same
{
p=q.top().second;
q.pop();
}
if(cal_mul>0)
nows=t2-1;
else
nows=t1;
tans=cal_mul*nows+cal_num;
if(tans>ans){
ans=tans;
anss=nows;
}
}
cout<<anss/10<<'.'<<anss%10<<' '<<ans/10<<'.'<<ans%10<<endl;
return 0;
}

/*

4
5
0 1 2 3 4
4
1 2 3

0.5 2.5
*/

using namespace std;
int main(){}
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>

const double eps=1e-1;
struct _Main{
typedef long long ll;

template <typename Type>
char t;
while(!isdigit(t=getchar()));
a=t-'0';
while(isdigit(t=getchar())) {
a*=10;
a+=t-'0';
}
}
double left;
double ans[2];
double calc(){
double ret=0;
int i,j,k;
j=0;
for(i=0;i<m;i++){
while(j+1<n && fabs(d[j+1]+left-p[i])<fabs(d[j]+left-p[i])){
j++;
}
ret+=fabs(d[j]+left-p[i]);
}return ret;
}

int l,m,n;
int p[305],d[305];
_Main(){
double temp;
int i,j,k;
for(i=0;i<m;i++){
}
for(i=1;i<n;i++){
}
left=0;
ans[0]=calc();
ans[1]=left;

left=l-d[n-1];
temp=calc();
if(temp>ans[0]){
ans[0]=temp;
ans[1]=left;
}

for(i=1;i<n;i++){
for(j=0;j<m;j++){
left=p[j]-(d[i]-d[i-1])/2.0-d[i-1];
if( left>-eps && (left +d[n-1]  < l+eps )){
temp=calc();
if(temp>ans[0]+eps || ((temp>ans[0]-eps) && left<ans[1]-eps)){
ans[0]=temp;
ans[1]=left;
}
}
}
}
printf("%.1lf %.1lf",ans[1],ans[0]);
fclose(stdout);
}

}boat;
//反正出题人给的std就是这个，这是个什么东西我也不知道，我也不敢问。
//也不知道能不能运行。