买二赠一--蓝桥

80%版本

我认为买的越大越好--贪心然后标记赠的

#include <bits/stdc++.h> using namespace std; typedef long long ll ; const long long INF = 1e18; const int MOD = 1e9 + 9; // 定义模数 ll n,m,k,t; //不开long long 见祖宗 bool bo[500111]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; vector<int> a; for(int i=0;i<n;i++) { int x;cin>>x;a.push_back(x); } sort(a.begin(),a.end()); ll c=0; for(int i=n-1;i>=0;i--) { if(!bo[i]) { c+=a[i]; //cout<<a[i]<<endl; int s;int f=0; for(int j=i-1;j>=0;j--) { if(!bo[j]) { c+=a[j]; bo[j]=true; s=a[j]; //cout<<s<<endl; for(int w=j-1;w>=0;w--) { if(bo[w]==false&&a[w]<=(double)s/2) { bo[w]=true; //cout<<a[w]<<endl; f=1; break; } } if(f) break; } if(f) break; } } } cout<<c; return 0; }

100%版本---加了个二分就行了

#include <bits/stdc++.h> using namespace std; typedef long long ll ; const long long INF = 1e18; const int MOD = 1e9 + 9; // 定义模数 ll n,m,k,t; //不开long long 见祖宗 bool bo[500111]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; vector<int> a; for(int i=0;i<n;i++) { int x;cin>>x;a.push_back(x); } sort(a.begin(),a.end()); ll c=0; for(int i=n-1;i>=0;i--) { if(!bo[i]) { c+=a[i]; //cout<<a[i]<<endl; int s;int f=0; for(int j=i-1;j>=0;j--) { if(!bo[j]) { c+=a[j]; bo[j]=true; s=(double)a[j]/2; //cout<<a[j]<<endl; int l=0,r=j-1; while(l<=r) { int mid=(l+r)>>1; if(a[mid]<=s&&bo[mid]==false) { l=mid+1; }else r=mid-1; } //cout<<"**"<<a[r]<<"**"<<endl; bo[r]=true; f=1; if(f) break; } if(f) break; } } } cout<<c; return 0; }