璨与序列 题解(stl,dfs)

描述

璨有一个长度为n的整数序列a1​,a2​,…,an​。
不过他想重新排序这个序列(也可以保持原序列)，把这个序列变成每个元素ai​(2≤i≤n)
都恰好是前一个元素的二倍或前一个元素的三分之一。

输入描述

第一行包含整数n。
第二行包含n个整数 a1​,a2​,…,an​。

输出描述

如果存在方案，则输出"Can is happy!"，然后输出一行n个整数，表示排序后的序列。输出任意合法方案即可。
否则输出，"Can is sad."

用例输入 1

4
42 28 84 126

用例输出 1

Can is happy!
126 42 84 28

用例输入 2

3
2 2 3

用例输出 2

Can is sad.

提示

数据范围
所有测试点满足 2≤n≤50，1≤ai​≤3×1018。

代码:

//计算机脑袋只是筛选
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxj=100;
int a[maxj],n;
multiset<int>s;
vector<int>ans;
bool dfs(vector<int>t,multiset<int>st){//dfs有形参,需要递归分治操作
    if(t.size()==n){
        ans=t;
        return true;
    }//分治结束
    int x=t.back();
    if(st.count(x*2)){
        t.push_back(x*2);
        s.erase(s.find(x*2));
        if(dfs(t,st))return true;//判断行还是不行
        t.pop_back();//不行就消除影响
        st.insert(x*2);
    }else if(x%3==0&&st.count(x/3)){
        t.push_back(x/3);
        s.erase(s.find(x/3));
        if(dfs(t,st))return true;
        t.pop_back();
        st.insert(x/3);
    }
    return false;
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        s.insert(x);
    }
    
    ans.push_back(*s.begin());
    if(dfs(ans,s)){//判断计算
        cout<<"Can is happy!"<<'\n';
    for(auto i:ans){
        cout<<i<<' ';
    }cout<<' ';
   
    }
    else{cout<<"Can is sad."<<'\n'; }
    
    return 0;
}