题目描述
阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。
阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。
输入格式
第一行有一个正整数N，表示螺丝街住户的数量。
接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤.≤Sn＜10^8
接下来的一行有N个正整数,其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai＜10^3
输出格式
输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。
输入样例
5
1 2 3 4 5
1 2 3 4 5
输出样例
15
19
22
24
25
数据规模
对于20%的数据，1≤N≤20；
对于40%的数据，1≤N≤100；
对于60%的数据，1≤N≤1000；
对于100%的数据，1≤N≤100000。
#include<stdio.h>
long MAX(long a,long b)
{
return a>b?a:b;
}
int main()
{
long N;
scanf("%ld",&N);
long a[2][N],i,max,k,b[2][N],flag,j,m,max0,X,record,flag0,distance;
for(i=0;i<2*N;i++)
{
if(i<N) scanf("%ld",&a[0][i]);
else if(i<2*N) scanf("%ld",&a[1][i-N]);
}
max=0;
for(k=0;k<N;k++)
{
max=max>(2*a[0][k]+a[1][k])?max:(2*a[0][k]+a[1][k]);
if (max==2*a[0][k]+a[1][k])
{
flag=k;
}
}
printf("%ld\n",max);
b[0][flag]=a[0][flag];
b[1][flag]=a[1][flag];
record=a[1][flag];
a[1][flag]=0;
for(X=2;X<=N;X++)
{
max0=0;
m=flag;
distance=a[0][flag];
for(j=0;j<N;j++)
{
m=flag;
if(a[0][j]<a[0][flag])
{
max0=max0>(a[1][j]+max)?max0:(a[1][j]+max);
if(max0==(a[1][j]+max)) flag0=j;
}
if(a[0][j]>a[0][flag])
{
max0=max0>(2*a[0][j]+a[1][j]+record)?max0:(2*a[0][j]+a[1][j]+record);
if(max0==(2*a[0][j]+a[1][j]+record)) {
flag0=j;
distance=a[0][j];
}
}
}
max=max0;
record=max-2*distance;
printf("%ld\n",max);
a[1][flag0]=0;
}
return 0;
}
整理了一下代码
#include<stdio.h>
long MAX(long a,long b)
{
return a>b?a:b;
}
int main()
{
long N;
scanf("%ld",&N);
long a[2][N];//存输入的两行数据
long flag,flag0;//存数组下标，前者存上次取最大值的数所对应的下标，后者存这次取最大值的数所对应的下标
long max0,max;
long i,k,X,j,m;
long record;//记录每次的疲劳度
long distance;//存每次最远的距离
for(i=0;i<2*N;i++)
{
if(i<N) scanf("%ld",&a[0][i]);
else if(i<2*N) scanf("%ld",&a[1][i-N]);
}//读入数据
max=0;
for(k=0;k<N;k++)
{
max=max>(2*a[0][k]+a[1][k])?max:(2*a[0][k]+a[1][k]);
if (max==2*a[0][k]+a[1][k])
{
flag=k;
}
}
printf("%ld\n",max);//x=1时
record=a[1][flag];
a[1][flag]=0;
for(X=2;X<=N;X++)//x>=2时
{
max0=0;
m=flag;
distance=a[0][flag];
for(j=0;j<N;j++)
{
m=flag;
if(a[0][j]<a[0][flag])//考虑距离小于原来最大距离的数集
{
max0=max0>(a[1][j]+max)?max0:(a[1][j]+max);
if(max0==(a[1][j]+max)) flag0=j;
}
if(a[0][j]>a[0][flag])//考虑距离大于原来最大距离的数集
{
max0=max0>(2*a[0][j]+a[1][j]+record)?max0:(2*a[0][j]+a[1][j]+record);
if(max0==(2*a[0][j]+a[1][j]+record)) {
flag0=j;
distance=a[0][j];
}
}
}
max=max0;
record=max-2*distance;//记录疲劳度
printf("%ld\n",max);
a[1][flag0]=0; //对取的数的疲劳度清零
}
return 0;
}
```