首页 > 试题广场 >

逃脱神凛幻域

[编程题]逃脱神凛幻域

热度指数：2522 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

受到小人的设计，主人公暮小云落入一个名为神凛幻域的奇特地方。对于迷失在这里的人而言这个空间没有绝对的方向，想要脱离这个地方就必须向前走出n步。由于在这个空间内没有方向的概念，无论何时向任何方向迈出一步都是等效的（哪怕你是原地转圈，只要走出N步即可脱离幻境）。不过，由于空间壁垒的原因，不同时刻向不同方向走所耗费的体力不同。现在已知不同时刻向某个方向跨出一步所需耗费的体力，请你告诉暮小云怎么走最省体力，以及需要耗费的最小体力。

输入描述:

有多个输入样例，输入的第一行是样例个数T(1≤T≤50)。每个样例的第一行是一个整数n(1≤n≤100000)。紧接着是四行，依次表示东南西北四个方向的体力耗费情况，每行n个数字，分别表示第n步向该方向走需要花费的体力值xi(0≤xi≤1000000)。某一步的多个方向体力值均为最小值时按照东南西北的顺序取优先方向。

输出描述:

第一行输出需要的最小体力值，第二行输出行走方案分别用符号ESWN表示东南西北。

示例1

输入

1
15
54 66 60 24 100 24 2 67 74 80 55 61 1 51 78
6 52 18 100 95 10 14 15 55 1 8 70 33 2 63
44 24 28 43 52 8 18 58 16 93 67 80 16 33 20
79 2 47 53 88 88 25 59 89 45 89 45 3 72 52

输出

220
SNSEWWESWSSNESW

算法知识视频讲解

Python

华科平凡

python3解法

for _ in range(int(input())):
    length, directions = int(input()), [] # 将四个方向数组放到directions里保存
    for _ in range(4):
        directions.append(list(map(int, input().split())))
    min_method, min_value = "", 0
    for i in range(length):
        current_choice = [directions[0][i], directions[1][i], directions[2][i], directions[3][i]]
        min_value += min(current_choice)
        min_method += "ESWN"[current_choice.index(min(current_choice))] 
    print(min_value)
    print(min_method)

发表于 2019-02-24 14:39:50 回复(1)

向宇回桌

import java.util.*;

public class Main {
    private static final int MAX = 1000000 + 10;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- != 0) {
            int n = sc.nextInt();
            final char[] directions = {'E', 'S', 'W', 'N'};
            int[][] in = new int[4][n];
            for (int i = 0; i!=4; i++) {
                for (int j=0; j!=n; j++) {
                    in[i][j] = sc.nextInt();
                }
            }
            int ans = 0; StringBuilder sb = new StringBuilder();
            for (int i=0; i!=n; i++) {
                int minIndex = 0;
                for (int j=1; j!=4; j++) {
                    if (in[minIndex][i] > in[j][i]) {
                        minIndex = j;
                    }
                }
                ans += in[minIndex][i];
                sb.append(directions[minIndex]);
            }
            System.out.println(ans);
            System.out.println(sb.toString());
        }
        return;
    }
}

发表于 2019-01-26 03:36:32 回复(2)

C/C++

Senjie

#include<iostream>
using namespace std;
int a[1000000];
int b[1000000];
int c[1000000];
int d[1000000];
int main()
{
    int n,T,sum;
    cin>>T;
    while(T--)
    {
        sum=0;
        cin>>n;
        string st="";
        for(int i=0;i<n;cin>>a[i++]);
        for(int i=0;i<n;cin>>b[i++]);
        for(int i=0;i<n;cin>>c[i++]);
        for(int i=0;i<n;cin>>d[i++]);
        for(int i=0;i<n;i++)
        {
            if(a[i]<=b[i]&&a[i]<=c[i]&&a[i]<=d[i]){
                st+='E';
                sum+=a[i];
            }else if(b[i]<=c[i]&&b[i]<=d[i]){
                st+='S';
                sum+=b[i];
            }else if(c[i]<=d[i]){
                st+='W';
                sum+=c[i];
            }else{
                st+='N';
                sum+=d[i];
            }
        }
        cout<<sum<<endl<<st<<endl;
    }
}

发表于 2019-01-28 11:34:05 回复(0)

C/C++

抓紧进攻

很尴尬，结果忘了输出回车，然后就没过，还以为别的地方错了。。。

要是真的机试，没有这么详细的报错和测试用例，估计还要吃大亏，以后要注意了！！！！！

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int num;
    scanf("%d",&num);
    int n;
    string str;
    for(int i=0;i<num;i++)
    {
        scanf("%d",&n);
        int array[4][n];
        int count = 0;
        str = "";
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<n;k++)
            {
                scanf("%d",&array[j][k]);
            }
        }
        for(int j=0;j<n;j++)
        {
            int min = 1000001;
            int direct = 0;
            
            for(int k=0;k<4;k++)
            {
                if(min>array[k][j])
                {
                     min = array[k][j];
                     direct = k;
                } 
            }
            if(direct==0)
            {
                str += 'E';
            }
            if(direct==1)
            {
                str += 'S';
            }
            if(direct==2)
            {
                str += 'W';
            }
            if(direct==3)
            {
                str += 'N';
            }
            count += min;
        }
        printf("%d\n",count);
        cout<<str<<endl;
    }
}

发表于 2020-07-23 02:37:40 回复(0)

C/C++

昔遥暮云

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        string dir="ESWN",ans;
        ans.resize(n);
        vector<int> arr(n,INT_MAX); //滚动数组（保存最小值）
        for(int i=0;i<4;i++){
            for(int j=0;j<n;j++){
                int t;
                cin>>t;
                if(t<arr[j]){
                    arr[j]=t;   //最小步数
                    ans[j]=dir[i];  //记录方向
                }
            }
        }
        int sum=0;
        for(int i:arr){
            sum+=i;
        }
        cout<<sum<<endl<<ans<<endl;
    }
}

发表于 2020-07-13 11:19:25 回复(0)

Python

牛客124928456号

m=int(input())
l1=['E','S','W','N']
for i in range(m):
    s=0
    res=''
    n=int(input())
    ve=list(map(int,input().split()))
    vs=list(map(int,input().split()))
    vw=list(map(int,input().split()))
    vn=list(map(int,input().split()))
    for j in range(n):
        l=[ve[j],vs[j],vw[j],vn[j]]
        k=l.index(min(l))
        s=s+l[k]
        res=res+l1[k]
    print(s)
    print(res)

发表于 2020-06-12 16:01:30 回复(0)

C/C++

一个好听的名字

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int T = 0, i = 0, n = 0, j = 0, k = 0;
    cin >> T;
    for (i = 0; i < T; i++)  //T个案例
    {
        string ans = "";            //用来记录每一次选择的方向，方便最后输出
        long sum_HP = 0;         //用来表示最后得到的最小的体力值
        cin >> n;                               //需要进行n步，后面进行动态的数组申请
        long *E = new long[n + 1];
        long *S = new long[n + 1];
        long *W = new long[n + 1];
        long *N = new long[n + 1];
        long **A = new long*[4];                //通过A进行一个归拢，方便后面写代码，可以短一些
        A[0] = E;
        A[1] = S;
        A[2] = W;
        A[3] = N;
        for (j = 0; j < 4; j++)              //输入每个方向每一步的体力值
        {
            for (k = 0; k < n; k++)
            {
                cin >> A[j][k];
            }
        }
        for (j = 0; j < n; j++)  //进行每一步的最小值的搜索
        {
            int min_index = 0;
            long min_HP = 10000000;
            for (k = 0; k < 4; k++)   //在线搜索，进行替代
            {
                if (min_HP > A[k][j])   //注意大于号，保证相同时，是按照东南西北的顺序
                {
                    min_index = k;
                    min_HP = A[k][j];
                }
            }
            sum_HP += min_HP;
            switch (min_index)     //对最小位置进行一个匹配，对字符串进行拼接
            {
                case 0: ans = ans + "E"; break;
                case 1: ans = ans + "S"; break;
                case 2: ans = ans + "W"; break;
                case 3: ans = ans + "N"; break;
            }
        }
        cout << sum_HP << endl;
        cout << ans << endl;                   //输出之后，进行动态删除
        delete []E;
        delete []S;
        delete []W;
        delete []N;
        delete []A;
    }
    return 0;
}

发表于 2019-02-16 20:34:39 回复(0)

C/C++

牛客549207409号

#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
int T;
long long n,x1,x2,x3,x4;
while(std::cin>>T)
{
for(int i=0;i<T;i++)
{
std::cin>>n;
std::vector<long long>E;
std::vector<long long>S;
std::vector<long long>W;
std::vector<long long>N;
for(long long j=0;j<n;j++)
{
std::cin>>x1;
E.push_back(x1);
}
for(long long j=0;j<n;j++)
{
std::cin>>x2;
S.push_back(x2);
}
for(long long j=0;j<n;j++)
{
std::cin>>x3;
W.push_back(x3);
}
for(long long j=0;j<n;j++)
{
std::cin>>x4;
N.push_back(x4);
}
std::string s;
int count=0;
for(long long j=0;j<n;j++)
{
if(E[j]==S[j]&&(E[j]<=W[j]&&E[j]<=N[j]))
{
count+=E[j];
s+="E";
}
else if(E[j]==W[j]&&(E[j]<=S[j]&&E[j]<=N[j]))
{
count+=E[j];
s+="E";
}
else if(E[j]==N[j]&&(E[j]<=W[j]&&E[j]<=S[j]))
{
count+=E[j];
s+="E";
}
else if(S[j]==W[j]&&(S[j]<=E[j]&&S[j]<=N[j]))
{
count+=S[j];
s+="S";
}
else if(S[j]==N[j]&&(S[j]<=E[j]&&S[j]<=W[j]))
{
count+=S[j];
s+="S";
}
else if(W[j]==N[j]&&(W[j]<=E[j]&&W[j]<=S[j]))
{
count+=W[j];
s+="W";
}
else if(E[j]<S[j]&&E[j]<W[j]&&E[j]<N[j])
{
count+=E[j];
s+="E";
}
else if(S[j]<E[j]&&S[j]<W[j]&&S[j]<N[j])
{
count+=S[j];
s+="S";
}
else if(W[j]<S[j]&&W[j]<E[j]&&W[j]<N[j])
{
count+=W[j];
s+="W";
}
else
{
count+=N[j];
s+="N";
}

}
std::cout<<count<<std::endl;
std::cout<<s<<std::endl;
}
}
return 0;
}

发表于 2020-09-12 08:52:33 回复(0)

lsq_047

看到case测试里面输出一样，为什么还是不能通过

对应输出应该为:
694 ESWESEWESNWSWSWSSWNSWSNSENSSWSEWE 9 N 367 EENSSENWSENWWWEWSEESNS 240 EWEWWSWEEEN 1219 ESWEESNESNWSSNWEWWWENEWESSSSSSWSENEWNWWSSNNSEWNSWNWENWSEWSNWWWWEWWWS 1280 SSSEWNWWNNEWSSNENWNNEESWWSWWNSWNNNESNEEWENWNESSNSEWWWEEESSSWNNSSSN 1730 ESNEWSWWNWWSSWEWESSENEESESNWSSNSESNENNSEEWSWNNSEESWSNENEESNSSNSWSEWWSNWESEEWW
你的输出为:
694 ESWESEWESNWSWSWSSWNSWSNSENSSWSEWE9 N367 EENSSENWSENWWWEWSEESNS240 EWEWWSWEEEN1219 ESWEESNESNWSSNWEWWWENEWESSSSSSWSENEWNWWSSNNSEWNSWNWENWSEWSNWWWWEWWWS1280 SSSEWNWWNNEWSSNENWNNEESWWSWWNSWNNNESNEEWENWNESSNSEWWWEEESSSWNNSSSN1730 ESNEWSWWNWWSSWEWESSENEESESNWSSNSESNENNSEEWSWNNSEESWSNENEESNSSNSWSEWWSNWESEEWW

发表于 2020-07-17 16:21:01 回复(0)

牛客835494805号

#include <iostream>
using namespace std;
int p[1000005];
char c[1000005];
int main()
{
int t,n,ans;
char x[] = {'S','W','N'};
cin >> t;
while(t--)
{
ans = 0;
cin >> n;
for(int i = 0 ; i < n ; i++)
{
cin >> p[i];
c[i] = 'E';
}
int tem;
for(int i = 0 ; i < n*3 ; i++)
{
cin >> tem;
if(tem < p[i%n])
{
p[i%n] = tem;
c[i%n] = x[i/n];
}
if(i/n>=2)
ans+=p[i%n];
}
cout << ans << endl;
for(int i = 0 ; i<n; i++)
cout << c[i];
cout << endl;
}
return 0;
}

发表于 2020-06-24 00:19:46 回复(0)

冬雪香莹

#include<iostream>
#include<algorithm>
using namespace std;
int mi(int a,int b,int c,int d,char &y)
{
    int e=min(min(min(a,b),c),d);
    if(a==e)
    {
        y='E';
    }
    else if(b==e)
    {
        y='S';
    }
    else if(c==e)
    {
        y='W';
    }
    else
    {
        y='N';
    }
    return e;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a1[100001],a2[100001],a3[100001],a4[100001];
        for(int i=0;i<n;i++)
        {
            cin>>a1[i];
        }
        for(int i=0;i<n;i++)
        {
            cin>>a2[i];
        }
        for(int i=0;i<n;i++)
        {
            cin>>a3[i];
        }
        for(int i=0;i<n;i++)
        {
            cin>>a4[i];
        }
        char a[100001];
        long long int sum=0;
        for(int i=0;i<n;i++)
        {
            sum+=mi(a1[i],a2[i],a3[i],a4[i],a[i]);
        }
        cout<<sum<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<a[i];
        }
        cout<<endl;
    }
    return 0;
}

发表于 2019-04-25 09:27:34 回复(0)

C/C++

guandadashen

#include<iostream>
using namespace std;

int main()
{
    char d[4]={'E','S','W','N'};
    
    int T;
    cin >> T;
    for(int t = 0; t < T; t++)
    {
        int n;
        cin >> n;
        int* xi = new int[n]();
        string stategy(n,'E');
        
        int temp;
        for(int i = 0; i < n; i++)
        {
            cin >> temp;
            xi[i] = temp;
        }
        
        for (int dir = 0; dir < 3; dir++)
        {
            for(int i = 0; i < n; i++)
            {
                cin >> temp;
                if(temp < xi[i]) // better
                {
                    xi[i] = temp; //更新
                    stategy[i] = d[1+dir];
                }
            }
        }
        
        int r = 0;
        for(int i = 0; i < n; i++)
        {
            r += xi[i];
        }
        cout << r << endl << stategy << endl;
        delete []xi;
    }
    return 0;
}

发表于 2019-04-10 11:08:18 回复(0)

白日梦想家hzg

class Solution(object): def calc(self, a):
        res = a[0]
        idx=0  for i in range(len(a)): if res>a[i]:
                res=a[i]
                idx=i return res, idx def label(self, t): if t == 0: return 'E'  if t == 1: return 'S'  if t == 2: return 'W'  if t == 3: return 'N'   while True: try:
        a = Solution()
        n_sample = input() while n_sample:
            n_step = input()
            m_E = (raw_input()).split(' ')
            m_S = raw_input().split(' ')
            m_W = raw_input().split(' ')
            m_N = raw_input().split(' ')
            lst_e=map(int,m_E)
            lst_s = map(int, m_S)
            lst_w = map(int, m_W)
            lst_n = map(int, m_N)
            lst=[lst_e,lst_s,lst_w,lst_n]
            res=0  path=[]
            temp=[0,0,0,0] for i in range(n_step):
                temp[0]=lst[0][i]
                temp[1] = lst[1][i]
                temp[2] = lst[2][i]
                temp[3] = lst[3][i]
                res_v,res_i=a.calc(temp)
                res=res+res_v
                path.append(a.label(res_i)) print(res) print(''.join(path))
            n_sample=n_sample-1   except: break

发表于 2019-03-21 17:33:56 回复(0)

Python

Re:煙花ゼロから易冷

T = int(input())
for x in range(T):
    n = int(input())
    matrix = []
    for i in range(4):
        matrix.append(list(map(int, input().rstrip().split())))
    sum = 0
    way = []
    switch = {
        0:'E',
        1:'S',
        2:'W',
        3:'N',
    }
    for i1 in range(n):
        min = matrix[0][i1]
        loc = 0
        for i2 in range(4):
            if matrix[i2][i1] < min:
                min = matrix[i2][i1]
                loc = i2
        sum += min
        way.append(switch[loc])
    print(sum)
    print( ''.join(way) )

发表于 2019-03-15 12:06:07 回复(0)

马桶专家

#include <iostream>
#include <string>
using namespace std;

int main()
{
int n; //输入实例数
cin>>n;
for(int i=0;i<n;i++) //最外层循环，实例数循环
{
int m; //输入步数
cin>>m;
int mint[m]; //用于存储每一步花费的最小体力
char mind[m]; //用于存储最小体力的方向
for (int j=0;j<4;j++) //中层循环，4个方向循环
{
for(int k=0;k<m;k++) //内层循环，体力循环
{
int t; //输入体力
cin>>t;
if(j==0) //第一次输入。存入两个数组
{
mint[k]=t;
mind[k]='E';
}
else if(mint[k]>t) //如果花费体力比存储的小，则进行替换
{
mint[k]=t;
switch(j)
{
case 1:
mind[k]='S';
break;
case 2:
mind[k]='W';
break;
case 3:
mind[k]='N';
break;
default:
break;
}
}
}
}
int sum=0;
string sout;
for(int j=0;j<m;j++)
{
sum+=mint[j];
sout+=mind[j];
}
cout<<sum<<endl;
cout<<sout<<endl;
}
}

发表于 2019-03-09 13:48:48 回复(0)

WriteBug

public void main() {
        Scanner sc = new Scanner(System.in);
        char[] direction = { 'E', 'S', 'W', 'N' };
        StringBuilder sbBuilder;
        int[][] arr;
        // 样例数
        int t = sc.nextInt();
        while ((t--) != 0) {
            sbBuilder = new StringBuilder();
            // 总步数
            int sum = 0;
            // 整数n
            int n = sc.nextInt();
            arr = new int[6][n];
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = sc.nextInt();
                    if (arr[i][j] - arr[4][j] < 0) {
                        arr[4][j] = arr[i][j];
                        arr[5][j] = i;
                    }
                }
                if (i == 0) {
                    arr[4] = arr[0];
                }
            }
            while ((n--) > 0) {
                sum += arr[4][n];
                sbBuilder.insert(0, direction[arr[5][n]]);
            }
            System.out.println(sum);
            System.out.println(sbBuilder);
        }
    }

发表于 2019-01-23 18:34:08 回复(0)

maggey刘

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n, t, min;
int[] a = new int[400005];
String m;

n = in.nextInt();
while ((n--) > 0) {
min = 0;
m = "";
t = in.nextInt();
for (int i = 1; i <= (4 * t); i++) {
a[i] = in.nextInt();
}
for (int j = 1; j <= t; j++) {
//ESWN
if (a[j] <= a[j + t] && a[j] <= a[j + 2 * t] && a[j] <= a[j + 3 * t]) {
m += 'E';
min += a[j];
} else if (a[j + t] <= a[j] && a[j + t] <= a[j + 2 * t] && a[j + t] <= a[j + 3 * t]) {
m += 'S';
min += a[j + t];
} else if (a[j + 2 * t] <= a[j] && a[j + 2 * t] <= a[j + t] && a[j + 2 * t] <= a[j + 3 * t]) {
m += 'W';
min += a[j + 2 * t];
} else if (a[j + 3 * t] <= a[j] && a[j + 3 * t] <= a[j + 2 * t] && a[j + 3 * t] <= a[j + t]) {
m += 'N';
min += a[j + 3 * t];
}
}
System.out.println(min);
System.out.println(m);
}
}
}

发表于 2019-01-21 19:48:38 回复(0)

秋霁花开

//类似贪心算法求最优解，注意最后的输出即可

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main{
    static String minChoice(int e,int s,int w,int n) {
        String [] direction = {"E","S","W","N"};
        int [] cost = {e,s,w,n};
        int temp = e;
        String tempString = "E";
        for (int i = 1; i < 4; i++) {
            if (temp > cost[i]) {
                temp = cost[i];
                tempString = direction[i];
            }
//            System.out.println(i+"temp"+temp);
        }
//        System.out.println("tempString"+tempString);
        return tempString;
    }
    public static void main(String[] e){
      Scanner sca = new Scanner(System.in);
    int [] east = new int[1000000];
    int [] south = new int[1000000];
    int [] west = new int[1000000];
    int [] north = new int[1000000];
    int n = 0;
    int t = 0;
    int count;
    int cost;
    t = Integer.valueOf(sca.next());
    count = t;
      while (sca.hasNext() && count-->0) {
          String [] direction = new String[1000000];
          cost = 0;
          n = Integer.valueOf(sca.next());
          for (int i = 0; i < n; i++) {
                east[i] = Integer.valueOf(sca.next());
            }
          for (int i = 0; i < n; i++) {
                south[i] = Integer.valueOf(sca.next());
            }
          for (int i = 0; i < n; i++) {
                west[i] = Integer.valueOf(sca.next());
            }
          for (int i = 0; i < n; i++) {
                north[i] = Integer.valueOf(sca.next());
            }
          for (int i = 0; i < n; i++) {
                direction[i] = minChoice(east[i], south[i], west[i], north[i]);
//                System.out.println("direction"+direction[i]);
                switch (direction[i]) {
                case "E":
                    cost+=east[i];
                    break;
                case "S":
                    cost+=south[i];
                    break;
                case "W":
                    cost+=west[i];
                    break;
                case "N":
                    cost+=north[i];
                    break;

                default:
                    break;
                }
            }
          System.out.println(cost);
          for (int i = 0; i < n; i++) {
                System.out.print(direction[i]);
            }
          System.out.println("");
        }

    }
}

发表于 2019-01-18 11:14:24 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    static final String DIRECTION = "ESWN";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while ((t--) != 0) {
            int n = Integer.parseInt(br.readLine());
            int[][] x = new int[4][n];
            for (int i = 0; i < 4; i++) {
                String[] strs = br.readLine().split(" ");
                for (int j = 0; j < n; j++) {
                    x[i][j] = Integer.parseInt(strs[j]);
                }
            }

            StringBuilder sb = new StringBuilder();
            int res = 0;
            for (int i = 0; i < n; i++) {
                int tmp = 0;
                for (int j = 1; j < 4; j++) {
                    if (x[j][i] < x[tmp][i]) tmp = j;
                }
                res += x[tmp][i];
                sb.append(DIRECTION.charAt(tmp));
            }
            System.out.println(res);
            System.out.println(sb);
        }
    }
}

发表于 2019-01-17 20:19:59 回复(2)