CF1031
Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2)
CF1031A
CF1031A题意
现在你有两天的时间备考NOI，两天各有 \(a\) 小时，\(b\) 小时（时空扭曲）。
每天可以看若干份笔记。编号为 \(k\) 的笔记需要看 \(k\) 小时(请不要忽略，最后输出有用)。为了考得更好，你需要最大化看的笔记份数。请你求出最多能看多少份笔记。
注意，看过的笔记需要都不相同。即使是不在同一天看的。
\((1 \leq a, b \leq 10^9)\)。
CF1031A题解
这个显然从小到大的贪心选择 \(1\sim k\) 之间的笔记，然后对于第一天尽可能分配给 \(1\sim x\)，如果有一个笔记看了超时，不看时间还不够，那么就把之前时间为 \((\sum_{i=1}^xi)-a\) 的那篇笔记分给第二天即可满足条件。
CF1031A代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e6 + 10;
bool book[maxn];
int a, b;
vector<int> v1, v2;
signed main(){
a = read(); b = read();
int sum = a + b, tmp = 0,point = 1;
while(tmp + point <= sum){tmp += point;point++;}
tmp = 0;point--;
for(int i = 1;i <= point;i++){
if(tmp + i > a){book[i] = 1;book[tmp + i - a] = 0;break;}
if(tmp + i == a){book[i] = 1;break;}
book[i] = 1;tmp += i;
}
for(int i = 1;i <= point;i++){
if(book[i])v1.push_back(i);
else v2.push_back(i);
}
printf("%d\n",v1.size());for(int i : v1)printf("%d ",i);puts("");
printf("%d\n",v2.size());for(int i : v2)printf("%d ",i);puts("");
return 0;
}