传送门
先考虑 \(n=1\) 的情况
此时 \(k \in [\lceil \frac{a}{2} \rceil, a]\) 都合法
尝试推广到 \(n=2\)
令 \(a<b\) ,首先发现可行的 \(k\) 的上界是 \(a+b\) ,可以用这个数减去不合法的
然后不合法区间就是 \([1, \lceil \frac{a}{2} \rceil-1]\) 及(如果 \(a < \lceil \frac{b}{2} \rceil\) ) \([a+1, \lceil \frac{b}{2} \rceil-1]\)
尝试推广到更高维,发现要让空缺区间尽量小,所以把 \(a\) 换成前面元素的前缀和
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 100010 #define ll long long #define reg register int //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n; ll a[N], tot, minn=(ll)(1e18); namespace force{ bool check(ll k) { int lim=1<<n; ll sum; for (int s=1; s<lim; ++s) { sum=0; for (int i=0; i<n; ++i) if (s&(1<<i)) sum+=a[i+1]; if (sum>=k && sum<=k*2) return 1; } return 0; } void solve() { int ans=0; for (int i=1; i<=tot; ++i) if (check(i)) ++ans; printf("%d\n", ans); exit(0); } } namespace task1{ void solve() { sort(a+1, a+n+1); if ((ll)(ceil((1.0*a[1])/2.0-1e-8))-1 > 0) tot-=(ll)(ceil((1.0*a[1])/2.0-1e-8))-1; for (int i=2; i<=n; ++i) { //cout<<"i: "<<i<<endl; //cout<<(ll)(ceil((1.0*a[i])/2.0-1e-8))-a[i-1]-1<<endl; //cout<<((ll)(ceil((1.0*a[i])/2.0-1e-8)))<<' '<<a[i-1]<<endl; if ((ll)(ceil((1.0*a[i])/2.0-1e-8))-a[i-1]-1 > 0) tot-=(ll)(ceil((1.0*a[i])/2.0-1e-8))-a[i-1]-1; a[i]+=a[i-1]; } //ll x=a[1], y=a[2]; //cout<<(ll)(ceil((1.0*x)/2.0-1e-8))-1<<' '<<(ll)(ceil((1.0*y)/2.0-1e-8))-x<<endl; //if ((ll)(ceil((1.0*x)/2.0-1e-8))-1 > 0) tot-=(ll)(ceil((1.0*x)/2.0-1e-8))-1; //if ((ll)(ceil((1.0*y)/2.0-1e-8))-x-1 > 0) tot-=(ll)(ceil((1.0*y)/2.0-1e-8))-x-1; printf("%lld\n", tot); //printf("%lld\n", tot-(ll)(ceil((1.0*minn)/(2.0)-1e-8))+1); //cout<<"l: "<<(ll)(ceil((1.0*minn)/(2.0)-1e-8))<<endl; exit(0); } } signed main() { n=read(); for (int i=1; i<=n; ++i) a[i]=read(), tot+=a[i], minn=min(minn, a[i]); //force::solve(); task1::solve(); return 0; }