题解 小L的疑惑

传送门

先将原序列排序,发现若前 \(k\) 个数能拼出的范围 \([1, r]\) 中 \(r\geqslant a_{k+1}-1\)
则值域可以连接起来,成为 \([1, r] \cup [a_{k+1}-1, r+a_{k+1}]\)
于是就做完了

Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long 
#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;
int a[N];

namespace force{
	bool able[N];
	void solve() {
		int lim=1<<n;
		for (int s=1; s<lim; ++s) {
			int sum=0;
			for (int i=0; i<n; ++i) if (s&(1<<i)) {
				sum+=a[i+1];
			}
			able[sum]=1;
		}
		for (int i=1; ; ++i) if (!able[i]) {printf("%lld\n", i); break;}
		exit(0);
	}
}

namespace task1{
	void solve() {
		sort(a+1, a+n+1);
		if (a[1]!=1) {puts("1"); exit(0);}
		int lim=1;
		for (int i=2; i<=n; ++i) {
			if (lim<a[i]-1) {printf("%lld\n", lim+1); exit(0);}
			lim+=a[i];
		}
		printf("%lld\n", lim+1);
		exit(0);
	}
}

signed main()
{
	freopen("math.in", "r", stdin);
	freopen("math.out", "w", stdout);

	n=read();
	for (int i=1; i<=n; ++i) a[i]=read();
	// force::solve();
	task1::solve();

	return 0;
}
上一篇:求一个字符串中最长单词,并将这个单词输出


下一篇:UnsupportedOperationException