首页 > 试题广场 >

绝域之门

[编程题]绝域之门
  • 热度指数：691 时间限制：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
算法知识视频讲解
添加回答
机器学习一个头像 机器学习一个
每种字符串的吸引值只与它第一次出现和最后一次出现的位置有关，所以我们可以先把所有字符串的首尾出现位置确定，再把其余的字符串塞到中间就行了，安排字符串位置时均按照字典序由小到大的顺序。 

#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)
牛客118647号头像 牛客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头像 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)
BanyanR头像 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号头像 牛客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)
dader头像 dader
总感觉牛客的在线编程讨论氛围不是很好，大家都是把代码放上去，希望能加一些解释，也希望牛客可以自己写写答案，毕竟都不算太难
发表于 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头像 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号头像 牛客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头像 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头像 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条回答 7985浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号