首页 > 试题广场 >

绝域之门

[编程题]绝域之门

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

经过多次强攻之后，赫柏带领的军团不仅没能击败鲁卡斯，反而被鲁卡斯打得七零八落，赫柏终于体会到了高阶天之驱逐者的强大实力。
不过，赫柏最终还是找到了鲁卡斯的致命弱点，他发现鲁卡斯喜欢收集上古卷轴，因为上古卷轴能够让鲁卡斯获得神秘之力。
卢卡斯决定使用上古卷轴将卢卡斯引诱到绝域之门，利用绝域之门的力量消灭卢卡斯。
赫柏注意到卢卡斯喜欢收集不同的卷轴，如果总是捡到相同的上古卷轴，它的兴趣就会逐渐降低。
赫柏现在拥有N种不同的卷轴，每种卷轴有Ai个。现在他要将这N个卷轴分散在鲁卡斯领地到绝域之门的路上，每一种排列方式都有一个吸引值Charm，吸引值越高，鲁卡斯被引诱到绝域之门的概率越高。
Charm=Sum of all D(i)，其中D(i)=k-i，i为该排列中卷轴i的下标，k为位于i后面且和i是同一种卷轴的卷轴下标。
现在所有的卷轴以<卷轴名称数量>的格式给出，你需要输出所有卷轴的排列顺序，使得吸引值最大，如果有多种排列方式满足条件，输出按照名字排列字典序最小的一个。

输入描述:

多组测试数据，请处理到文件结束。

对于每组测试数据：

第一行：一个整数N，代表有N种卷轴。

第二行：N种卷轴的描述。

保证：

0<=N<=50;

卷轴名称为长度1~10的字母，每种卷轴的数量为1~800之间的一个整数。

输出描述:

输出所有卷轴的一个排列。

示例1

输入

3
Thunder 1 Wind 3 Soil 2

输出

Soil Wind Thunder Wind Soil Wind

算法知识视频讲解

牛客118647号

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			int n = scan.nextInt();
            //TreeMap自然排序
			Map<String, Integer> charm=new TreeMap<String,Integer>();
			String key;int value;
			for (int i = 0; i < n; i++) {
				key = scan.next();
				value = scan.nextInt();
				charm.put(key, value);
			}
			System.out.println(getCharm(charm));
		}
	}

	// 一个串的charm 只和start，end 的index有关。
	public static String getCharm(Map<String, Integer> charm) {
		StringBuilder result = new StringBuilder();
		for(Map.Entry<String, Integer> item:charm.entrySet()){
			if(item.getValue()>=2){
				result.append(item.getKey()+" ");
				item.setValue(item.getValue()-2);
			}
		}
		String head=result.toString().trim();
		for(Map.Entry<String, Integer> item:charm.entrySet()){
			while(item.getValue()>0){
				result.append(item.getKey()+" ");
				item.setValue(item.getValue()-1);
			}
		}
		result.append(head);
		return result.toString();
	}
}

发表于 2016-08-06 19:32:30 回复(0)

inode

#include <iostream>  
#include <string>
#include <algorithm>
#include <vector> 
#include <map> 
using namespace std;
int main()  
{  
	int N;
	while(cin>>N)
	{
		
		map<string,int> m;
		int n = N;int num = 0;
		while(n)
		{
			int tmp ;
			string st;
			cin>>st>>tmp;
			m[st] = tmp;
			num += tmp;
			n--;
		}
		vector<string> res(num,"");
		int i = 0;
		map<string,int>::iterator iter = m.begin();
		vector<string> back;
		for(;iter!=m.end();iter++)
		{
			if (iter->second >= 2)
			{
				iter->second -= 2;
				res[i] = iter->first;
				i++;
				back.push_back(iter->first);
			}
		}
		int p = num-1;
		for(int j=back.size()-1;j>=0;j--) {
			res[p] = back[j];
			p--;
		}
		back.clear();
		for(iter = m.begin();iter!=m.end();iter++)
		{
			while(iter->second > 0)
			{
				back.push_back(iter->first);
				iter->second -- ;
			}
		}
		sort(back.begin(),back.end());
		for(int b=0;b<back.size();b++)
		{
			res[i] = back[b];
			i++;
		}
		for(i=0;i<num;i++)
		{
			cout<<res[i];
            if(i != num-1) cout<<" ";
		}
		cout<<endl;
	}
	return 0;  
}

发表于 2016-08-03 22:13:16 回复(0)

机器学习一个

每种字符串的吸引值只与它第一次出现和最后一次出现的位置有关，所以我们可以先把所有字符串的首尾出现位置确定，再把其余的字符串塞到中间就行了，安排字符串位置时均按照字典序由小到大的顺序。

#include<iostream>
#include <sstream>
#include<stdio.h>
#include<queue>
#include<list>
#include<set>
#include<map>
#include<time.h>
#include<vector>
#include<stack>
#include<unordered_set>
#include<unordered_map>
#include<memory.h>
#include<algorithm>
#include<numeric>
#include<string>
#include<functional>
#include<limits.h>
#include<iterator>
using namespace std;
#pragma warning(disable:4996)


int main(){
	int n;
	while (cin >> n){
		string l="", mid="", r="";
		vector<pair<string, int>>v(n);
		for (int i = 0; i < n; i++){
			cin >> v[i].first>>v[i].second;
		}
		sort(v.begin(), v.end());
		for (int i = 0; i < n; i++){
			if (v[i].second>1)
				l += v[i].first + ' ', r += v[i].first + ' ', v[i].second-=2;
		}
		for (int i = 0; i < n; i++){
			while (v[i].second>0)
				mid += v[i].first + ' ', v[i].second--;
		}
		string s = l + mid + r;
		if (s.size())
			s.pop_back();
		cout << s << endl;
	}
}

发表于 2016-06-23 09:49:11 回复(15)

BanyanR


	
	
		function ranal(R){
	

	
		var ans=0;
	

	
		for(var i=1;i*i<R;i++){
	

	
		var J=R-i*i;
	

	
		var j=Math.sqrt(J);
	

	
		if(j*j==J){
	

	
		ans++;
	

	
		}
	

	
		}
	

	
		return ans*4;
	

	
		}
	

	
		console.log(ranal(25));

发表于 2018-08-11 15:12:02 回复(0)

牛客1301431号

  #include<iostream> 

  #include <sstream> 

  #include<stdio.h> 

  #include<queue> 

  #include<list> 

  #include<set> 

  #include<map> 

  #include<time.h> 

  #include<vector> 

  #include<stack> 

  #include<unordered_set> 

  #include<unordered_map> 

  #include<memory.h> 

  #include<algorithm> 

  #include<numeric> 

  #include<string> 

  #include<functional> 

  #include<limits.h> 

  #include<iterator> 

  usingnamespacestd; 

  #pragma warning(disable:4996) 

  intmain(){ 

      intn; 

      while(cin >> n){ 

          string l="", mid="", r=""; 

          vector<pair<string, int>>v(n); 

          for(inti = 0; i < n; i++){ 

              cin >> v[i].first>>v[i].second; 

          } 

          sort(v.begin(), v.end()); 

          for(inti = 0; i < n; i++){ 

              if(v[i].second>1) 

                  l += v[i].first + ' ', r += v[i].first + ' ',
  v[i].second-=2; 

          } 

          for(inti = 0; i < n; i++){ 

              while(v[i].second>0) 

                  mid += v[i].first + ' ', v[i].second--; 

          } 

          string s = l + mid + r; 

          if(s.size()) 

              s.pop_back(); 

          cout << s << endl; 

      } 

  }

发表于 2016-09-28 12:26:35 回复(0)

chrisssssssssss

总感觉牛客的在线编程讨论氛围不是很好，大家都是把代码放上去，希望能加一些解释，也希望牛客可以自己写写答案，毕竟都不算太难

发表于 2016-09-10 15:29:06 回复(0)

弓长

import java.util.Arrays;

import java.util.Scanner;

public class Charm {

public static void main(String[] args) {

Scanner scan=new Scanner(System.in);

while(scan.hasNext()){

int n=scan.nextInt();

String[] name=new String[n];

int[] num=new int[n];

for(int i=0;i<n;i++){

name[i]=scan.next();

num[i]=scan.nextInt();

}

System.out.println(getCharm(name,num));

}

//一个串的charm 只和start，end 的index有关。

public static String getCharm(String[] name,int[] num){

StringBuilder result=new StringBuilder();

//Arrays.sort(name);

//System.out.println(name[0]);

StringBuilder sb=new StringBuilder();

for(int i=0;i<name.length;i++){//找出n>=2 的串

if(num[i]>=2){

sb.append(name[i]+" ");

num[i]-=2;

}

String[] head=sb.toString().trim().split(" ");//按字母顺序，拼接head

Arrays.sort(head);

for(int i=0;i<head.length;i++)

result.append(head[i]+" ");

StringBuilder sb2=new StringBuilder();//对剩下的str 按字母顺序拼接

for(int i=0;i<name.length;i++){

while(num[i]!=0){

sb2.append(name[i]+" ");

num[i]--;

}

String[] mid=sb2.toString().trim().split(" ");

Arrays.sort(mid);

String midstr=mid.toString();

for(int i=0;i<mid.length;i++)

result.append(mid[i]+" ");

for(int i=0;i<head.length;i++)//头尾相同，拼接尾部

result.append(head[i]+" ");

return result.toString().trim();

}

发表于 2016-08-05 15:17:54 回复(0)

SevenRoar

输出简单点，首尾顺序一样，中间按照字典序和个数一次输出即可

#include <algorithm>

#include <iostream>

#include <map>

using namespace std;

int main()

{

int n;

while(cin >> n)

{

map<string, int> arrange_scroll;

map<string, int> middle_scroll;

map<string, int> str_order;

for(int i=0; i<n; i++)

{

string s;

int nr;

cin >> s >> nr;

if(nr == 1)

middle_scroll[s] = nr;

else

arrange_scroll[s] = nr;

}

map<string, int>::iterator mip = arrange_scroll.begin();

while(mip != arrange_scroll.end())

{

if(mip == arrange_scroll.begin())

cout << mip->first;

else

cout << " " << mip->first;

mip->second -= 2;

str_order[mip->first] = mip->second;

mip ++;

}

arrange_scroll.insert(middle_scroll.begin(), middle_scroll.end());

mip = arrange_scroll.begin();

while(mip != arrange_scroll.end())

{

while(mip->second > 0)

{

cout << " " << mip->first;

mip->second --;

}

mip ++;

}

mip = str_order.begin();

while(mip != str_order.end())

{

cout << " " << mip->first;

mip ++;

}

cout << endl;

}

return 0;

}

发表于 2016-07-08 16:49:16 回复(0)

牛客658089号

import java.util.*;

public class Main{

public static void main(String[] arg0){

Scanner in = new Scanner(System.in);

while(in.hasNext()){

int n=in.nextInt();

List<String> l1=new ArrayList<String>();

List<String> l2=new ArrayList<String>();

int num=0;

while(n-->0){

String string=in.next();

num+=string.length()+1;

int count=in.nextInt();

if(count>=2){

l1.add(string);

count-=2;

}

while(count-->0){

l2.add(string);

}

Collections.sort(l1);

Collections.sort(l2);

StringBuilder sBuilder=new StringBuilder();

for(String ss:l1) sBuilder.append(ss+" ");

for(String ss:l2) sBuilder.append(ss+" ");

for(String ss:l1) sBuilder.append(ss+" ");

//sBuilder.setLength(num);

System.out.print(sBuilder.toString());

System.out.print("\0");

}

输出怎么弄，我感觉我的算法没问题，是这系统太坑人了么，花了3个小时在输出输入上面了，tm的，为什么要手动加’\0‘，不加tm输出一大推东西，加了又说计算了一组数据，tm的这垃圾系统，比Leetcoder差多了

发表于 2016-07-07 13:23:41 回复(5)

Shawn_Mei


	/*参考之前那个哥们的写一个用JAVA实现的吧*/



	import java.util.AbstractMap;



	import java.util.ArrayList;



	import java.util.Collections;



	import java.util.Comparator;



	import java.util.HashMap;



	import java.util.Iterator;



	import java.util.Map;



	import java.util.Map.Entry;



	import java.util.Scanner;



	



	public class Main {



	 public static void main(String []args ) {



	 Scanner in=new Scanner(System.in);



	 while (in.hasNext()) {



	 ArrayList<Map.Entry<String, Integer>> list=new ArrayList<Map.Entry<String, Integer>>();



	 int num=in.nextInt();



	 for (int i = 0; i < num; i++) {



	 String str=in.next();



	 int times=in.nextInt();



	 Map.Entry<String, Integer> pair = new AbstractMap.SimpleEntry(str, times); 



	 list.add( pair);



	 }



	 Comparator<Map.Entry<String, Integer>> cmp=new Comparator<Map.Entry<String,Integer>>() {



	



	 @Override



	 public int compare(Entry<String, Integer> o1,



	 Entry<String, Integer> o2) {



	 // TODO Auto-generated method stub



	 return o1.getKey().compareTo(o2.getKey());



	 }



	 };



	 Collections.sort(list, cmp);



	 String f="";



	 String mid="";



	 String l="";



	 for (int i = 0; i < num; i++) {



	 if (list.get(i).getValue()>1) {



	 f=f+list.get(i).getKey()+" ";



	 l=l+list.get(i).getKey()+" ";



	 list.get(i).setValue(list.get(i).getValue()-2);



	 }



	 }



	 for (int i = 0; i < num; i++) {



	 while(list.get(i).getValue()>0) {



	 mid=mid+list.get(i).getKey()+" ";



	 list.get(i).setValue(list.get(i).getValue()-1);



	 }



	 }



	 String res=f+mid+l; 



	 System.out.println(res.trim());



	 



	 }



	 }



	}

发表于 2016-06-27 11:14:13 回复(0)

远方的范特西

//测试通过的正确代码，注意考虑输入的测试值为空的情况
// letv621_3_2.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
//#include <utility>
using namespace std;

bool cmp(pair<string, int> p1, pair<string, int> p2)
{
	return p1.first < p2.first;
}

void getPermutation(vector<pair<string, int>> str)
{
	sort(str.begin(), str.end(), cmp);
	int i;
	int n = str.size();
	string start, end, middle;
	for (i = 0; i < n; i++)
	{
		if (str[i].second > 1)
		{
			//if()
			start.append(str[i].first+" ");
			end.append(str[i].first + " ");
			str[i].second -= 2;
		}
	}
	for (i = 0; i < n; i++)
	{
		int n = str[i].second;
		for (int j = 0; j < n; j++)
		{
			middle.append(str[i].first + " ");
		}
	}
	start = start + middle + end;
    if(start.size())//这里要检测start是否为空
	start.erase(start.size() - 1);
	cout << start << endl;
}

int main()
{
	vector<pair<string,int>> str;
	int n;
	while (cin >> n)
	{
        
		for (int i = 0; i < n; i++)
		{
			string strTmp;
			int a;
			cin >> strTmp;
			cin >> a;
			pair<string, int> p(strTmp, a);
			str.push_back(p);			
		}
		getPermutation(str);
        str.clear();
       /*vector<pair<string,int>>::iterator it;
        while(str.size()>0)
        {
            it=str.begin();
            str.erase(it);
        }*/
	}
    return 0;
}






// letv622_3.cpp : 定义控制台应用程序的入口点。
//沃日，我是把所有排列的情况都遍历了一遍，然后一个个判断，找出满足提议的
//实际上是类似于输出1，2,3,4，。。。。，n的全排列
//在这里运行是会超时的。
// letv622_3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int getCharm(vector<string> vStr, vector<int> arrInt)
{
	vector<string> vStr2;
	for (int i = 0; i < vStr.size(); i++)
	{
		vStr2.push_back(vStr[arrInt[i]]);
	}
	int begin = 0;
	int charm = 0;
	vector<string> sTmp;
	while (true)
	{
		int j = begin;
		string tmp = vStr2[j];
		sTmp.push_back(tmp);
		for (int i = j+1; i < vStr2.size(); i++)
		{
			if (vStr2[i] == tmp)
			{
				charm += i - j;
				j = i;
			}
		}
		int i1;
		for (i1 = begin+1; i1 < vStr2.size(); i1++)
		{
			bool flag = true;
			for (int m = 0; m < sTmp.size(); m++)
			{
				if (vStr2[i1] == sTmp[m])
				{
					flag = false;
					break;
				}
			}	
			if (flag == true)
			{
				begin = i1;
				break;
			}
		}
		if (i1 == vStr2.size())
		{
			return charm;
		}
	}
}

void copy(vector<int> & arrMax, vector<int> arrDes)
{
	arrMax.clear();
	for (int i = 0; i < arrDes.size(); i++)
	{
		arrMax.push_back(arrDes[i]);
	}
}

void getArrange(vector<string> vStr)
{
	vector<int> arrMax;
	vector<vector<int>> arrInt[2];
	int charm = 0;
	vector<int> t1 = { 0 };
	vector<int> t2 = { 0 };
	arrInt[0].push_back(t1);
	arrInt[1].push_back(t2);
	int n = vStr.size();
	int i = 1;
	while (true)
	{
		while (i != n)
		{
			vector<int> t1;
			copy(t1, *(arrInt[0].end() - 1));
			t1.push_back(i);
			int s = (*(arrInt[0].end()-1)).size();
			vector<int> t2 = { s };
			arrInt[0].push_back(t1);
			arrInt[1].push_back(t2);
			i++;
		}
		int pos = n - 2;
		while (true)
		{
			for (int i = 0; i < (*(arrInt[0].end() - 1)).size(); i++)
			{
				if (i != (*(arrInt[0].end() - 1)).size())
					cout << (*(arrInt[0].end() - 1))[i] << " ";
				else
					cout << (*(arrInt[0].end() - 1))[i];
			}
			cout << endl;
			int tmpCharm = getCharm(vStr, *(arrInt[0].end()-1));
			if (charm == tmpCharm)
			{
				string c;
				string t;
				for (int i = 0; i < arrMax.size(); i++)
				{
					c += vStr[arrMax[i]];
					t += vStr[(*(arrInt[0].end() - 1))[i]];
				}
				if (c > t)
				{
					copy(arrMax, *(arrInt[0].end() - 1));
				}
			}
			if (charm < tmpCharm)
			{
				charm = tmpCharm;
				copy(arrMax, *(arrInt[0].end() - 1));
			}
			if (pos == -1)
			{
				break;
			}
			int tmp = (*(arrInt[0].end() - 1))[pos + 1];
			(*(arrInt[0].end() - 1))[pos + 1] = (*(arrInt[0].end() - 1))[pos];
			(*(arrInt[0].end() - 1))[pos] = tmp;
			pos--;
		}
		vector<vector<int>>::iterator it1,it2;
		it1 = arrInt[0].end() - 1;
		arrInt[0].erase(it1);
		it2 = arrInt[1].end() - 1;
		arrInt[1].erase(it2);

		it1 = arrInt[0].end() - 1;		
		it2 = arrInt[1].end() - 1;
		while ((*it2)[0] == 0)
		{
			arrInt[0].erase(it1);			
			arrInt[1].erase(it2);
			if (arrInt[0].size() == 0)
			{
				break;
			}
			it1 = arrInt[0].end() - 1;
			it2 = arrInt[1].end() - 1;
		}
		if (arrInt[0].size() == 0)
		{
			break;
		}
		int pos1 = (*it2)[0];
		int tmp = (*(arrInt[0].end() - 1))[pos1 - 1];
		i = (*(arrInt[0].end() - 1)).size();
		(*(arrInt[0].end() - 1))[pos1 - 1] = (*(arrInt[0].end() - 1))[pos1];
		(*(arrInt[0].end() - 1))[pos1] = tmp;
		(*it2)[0]= (*it2)[0] -1;
		
	}
	for (int i = 0; i < arrMax.size(); i++)
	{
		if(i!= vStr.size())
			cout<<vStr[arrMax[i]]<<" ";
		else
			cout << vStr[arrMax[i]];		
	}
	cout << endl;
}

int main()
{
	int n;
	vector<string> vStr;
	vector<int> arrInt = {0,2,4,7,5,1,6,3};
	while (cin >> n)
	{
		for (int i = 0; i < n; i++)
		{
			string tmp;
			int m;
			cin >> tmp;
			cin >> m;
			for(int j = 0; j < m; j++)
			{
				vStr.push_back(tmp);
			}
		}
		getArrange(vStr);
	}
	

    return 0;
}

编辑于 2016-06-30 17:23:44 回复(0)

lzytj

答案错误:您提交的程序没有通过所有的测试用例

case通过率为0.00%
测试用例:
3
Shakira 1 Jamiroquai 3 Gorillaz 2

对应输出应该为:

Gorillaz Jamiroquai Jamiroquai Shakira Gorillaz Jamiroquai

你的输出为:

Gorillaz Jamiroquai Shakira Jamiroquai Gorillaz Jamiroquai

我这是题目意思没看懂么，有人解释一下吗

发表于 2016-06-23 16:32:57 回复(5)

提交观点

问题信息

C++工程师 2017 字符串乐视排序 Java工程师

来自：乐视2017暑期实习生...

难度：

12条回答 85收藏 8170浏览

通过挑战的用户

AUV喽

2021-01-12 14:55:43
槡槡

2020-02-29 15:08:14
ToNeToNe

2019-07-07 10:11:24
tutu95

2019-04-18 23:24:25
shala

2018-01-31 12:24:27

绝域之门

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题