A. Phoenix and Gold
分析: 直接遍历,因为所有的物品各不相同,所以如果遇到前缀和为 x x x的情况直接交换某一项和下一项即可。如果所有物品的和为 x x x,那么无论如何都不满足题意,直接输出 NO \text{NO} NO。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int t,n,a[N],x;
int main(){
cin>>t;
while(t--){
int sum=0;
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
if(sum==x) cout<<"NO"<<endl;
else{
sum=0;
cout<<"YES"<<endl;
for(int i=1;i<=n;i++){
if(sum+a[i]==x){
swap(a[i],a[i+1]);
}
sum+=a[i];
cout<<a[i]<<" ";
}
cout<<endl;
}
}
}
B. Phoenix and Puzzle
分析: 首先判断是否能被 2 2 2和 4 4 4整除,因为只有 2 2 2和 4 4 4可以拼成一个小正方形,再判断 n / 2 n/2 n/2或 n / 4 n/4 n/4是否为平方数即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int t,n;
map<int,int> pd;
void init(){
for(int i=1;i*i<=1e9;i++){
pd[i*i]=1;
}
}
int main(){
init();
cin>>t;
while(t--){
cin>>n;
if(n%2==0&&pd[n/2]||n%4==0&&pd[n/4]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
C. Phoenix and Towers
分析: 先把每个塔放入小根堆, 每次往堆顶放入方块,最后判断一下最大的塔和最小的塔差值是否为 x x x即可。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,m,x,h[N],ans[N],res;
struct node{
int x,id;
bool operator<(const node num)const{
return x>num.x;
}
}tower[N];
int main(){
cin>>t;
while(t--){
memset(tower,0,sizeof tower);
res=0;
int flag=0,mx=0,mi=2e9;
priority_queue<node> q;
cin>>n>>m>>x;
for(int i=1;i<=m;i++){
node k;
k.x=tower[i].x;
k.id=i;
q.push(k);
}
for(int i=0;i<n;i++){
cin>>h[i];
auto t=q.top();
q.pop();
t.x+=h[i];
ans[res++]=t.id;
q.push(t);
}
for(int i=1;i<=m;i++){
mx=max(mx,tower[i].x);
mi=min(mi,tower[i].x);
}
if(mx-mi>x) cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
for(int i=0;i<res;i++) cout<<ans[i]<<" ";
cout<<endl;
}
}
}