P8148 声海 | Sea of Voices 题解

FFTotoro · 2022-02-13 21:41:58 · 题解

考虑使用较为暴力的做法。

输入一排数据，排序后用一个 std::vector 存放答案，先放入第一个元素和第二个元素，然后从第三个元素开始枚举，如果是若干个已选择的元素之和则不选，否则压入 std::vector。

实现时需要注意一些细节。具体的实现见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  int s=n*(n+1)/2,c=0;
  vector<int> a(s),b(n+1);
  for(auto &i:a)cin>>i;
  sort(a.begin(),a.end()); // 排序
  vector<int> v={a[0],a[1]}; // 存放最终答案
  for(int i=2;i<s;i++){ // 从前扫到后
    bool f=false;
    for(int j=2;j<=v.size();j++){ // 枚举区间长度
      for(int k=b[j];k<=v.size()-j;k++){ // 枚举左端点
        for(int l=k;l<k+j;l++)c+=v[l]; // 暴力加和
        if(c==a[i]){b[j]++,c=0,f=true; break;} // 说明是多个数的和，跳出循环
        if(c>a[i]){c=0; break;} // 特判优化，如果总和超过了当前枚举的元素，继续枚举下去也没有意义了，和只会越来越大
      }
      if(f)break;
    }
    if(!f){
      v.push_back(a[i]);
      if(v.size()==n)break; // 特判，如果个数够了就跳出循环
    }
  }
  for(int i:v)cout<<i<<' ';
  cout<<endl;
  return 0;
}