璨与序列 题解(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;
}