NC14410. 学姐肝手游
描述
输入描述
输入只有1行。
输入5个字符串，每个字符串包含两个字符，第一个字符是'Q','A','B'，代表卡的类型，第二个字符是'1','2','3'，代表卡的所属从者。
输出描述
输出一行，包括3个字符串，每个字符串包含两个字符，第一个字符是'Q','A','B'，代表卡的类型，第二个字符是'1','2','3'，代表卡的所属从者。并且保证该方案是伤害最大的，如果存在多个解，输出字典序最小的解。
示例1
输入:
A2 A3 A1 A1 Q2
输出:
A1 A1 A2
说明:
按顺序选择第1名从者的A卡，第1名从者的A卡，第2名从者的A卡，可以造成最大伤害。示例2
输入:
A1 A1 Q1 Q2 Q2
输出:
Q1 A1 A1
说明:
按顺序选择第1名从者的Q卡，第1名从者的A卡，第1名从者的A卡，可以造成最大伤害（此组合引发了“额外攻击”）。C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 464K, 提交时间: 2022-11-09 19:59:18
#include<bits/stdc++.h>
using namespace std;
const int N=10;
string s[N];
int st[N],a[N];
vector<string>v;
double ans;
double calc()
{
string res1=s[a[1]];
string res2=s[a[2]];
string res3=s[a[3]];
double sum=0;
double flag=1;
if(res1[0]=='B')
{
flag=1.5;
sum+=1.5;
}
else if(res1[0]=='A') sum+=1.0;
else sum+=0.8;
if(res2[0]=='B') sum+=flag*1.5*1.2;
else if(res2[0]=='A') sum+=flag*1.0*1.2;
else sum+=flag*0.8*1.2;
if(res3[0]=='B') sum+=flag*1.5*1.4;
else if(res3[0]=='A') sum+=flag*1.0*1.4;
else sum+=flag*0.8*1.4;
if(res1[1]==res2[1] && res2[1]==res3[1])
{
sum+=flag*1.0;
}
return sum;
}
bool check()
{
string res1;
string res2;
for(int i=1;i<=3;i++) res1+=s[a[i]];
for(auto x:v) res2+=x;
return res1<res2;
}
void dfs(int u)
{
if(u>3)
{
double res=calc();
if(res>ans)
{
ans=res;
v.clear();
for(int i=1;i<=3;i++) v.push_back(s[a[i]]);
}
else if(res==ans)
{
if(check())
{
v.clear();
for(int i=1;i<=3;i++) v.push_back(s[a[i]]);
}
}
return ;
}
for(int i=1;i<=5;i++)
{
if(!st[i])
{
st[i]=1;
a[u]=i;
dfs(u+1);
st[i]=0;
}
}
}
signed main()
{
for(int i=1;i<=5;i++) cin>>s[i];
dfs(1);
for(auto x:v) cout<<x<<" ";
return 0;
}
Java 解法, 执行用时: 34ms, 内存消耗: 10956K, 提交时间: 2022-03-01 15:54:39
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static String s[]=new String[5];
static boolean st[]=new boolean[5];
static String ans="";
static double sum=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner(System.in);
for(int i=0;i<5;i++) {
s[i]=cin.next();
}
Arrays.sort(s);
dfs(0,"");
System.out.println(ans);
}
private static void dfs(int n, String sb) {
// TODO Auto-generated method stub
if(n==3) {
// System.out.println(sb);
double t=f(sb);
// System.out.println(t);
if(t>sum) {
sum=t;
ans=sb;
}else if(t==sum) {
if(sb.compareTo(ans)<0) {
ans=sb;
}
}
return;
}
for(int i=0;i<5;i++) {
if(!st[i]) {
st[i]=true;
if(n>0)dfs(n+1,sb+" "+s[i]);
else dfs(n+1,sb+s[i]);
st[i]=false;
}
}
}
private static double f(String sb) {
// TODO Auto-generated method stub
String ss[]=sb.split(" ");
// System.out.println(ss[0]);
double res=1;
double flag=0;
if(ss[0].charAt(0)=='B')flag=0.5;
for(int i=0;i<3;i++) {
double t=check(ss[i].charAt(0))+flag;
if(i==1)t*=1.2;
if(i==2)t*=1.4;
res+=t;
}
if(ss[0].charAt(1)==ss[1].charAt(1)&&ss[0].charAt(1)==ss[2].charAt(1))res+=check(ss[2].charAt(0));
return res;
}
private static double check(char c) {
// TODO Auto-generated method stub
if(c=='A')return 1;
if(c=='B')return 1.5;
if(c=='Q')return 0.8;
return 0;
}
}
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 612K, 提交时间: 2020-04-04 22:11:24
#include <iostream>
#include <algorithm>
using namespace std;
string date[5];
double calp(string a){
if(a[0]=='A'){
return 1;
}
else if(a[0]=='B'){
return 1.5;
}
else if(a[0]=='Q'){
return 0.8;
}
}
double cal(string a,string b,string c){
double ans=0;
int extra=0;
int go=0;
if(a[1]==b[1]&&b[1]==c[1]){
extra=1;
}
if(a[0]=='B') go=1;
double tmp;
ans+=calp(a);
ans+=calp(b)*1.2;
tmp=calp(c)*1.4;
ans+=tmp;
if(extra){
ans+=tmp;
}
if(go){
ans*=1.5;
}
return ans;
}
int main()
{
for(int i=0;i<5;i++){
cin>>date[i];
}
sort(date,date+5);
double ma=0;
string ans[3];
do{
string a,b,c;
a=date[0],b=date[1],c=date[2];
double pos=cal(a,b,c);
if(pos>ma){
ans[0]=a;
ans[1]=b;
ans[2]=c;
ma=pos;
}
}while(next_permutation(date,date+5));
for(int i=0;i<3;i++){
if(i) cout<<" ";
cout<<ans[i];
}
cout<<endl;
return 0;
}