Codeforces 1072 C - Cram Time

C - Cram Time

思路:首先找到最大的x,使得x*(x+1)/2 <= a+b

那么一定存在一种分割使得 a1 <= a 且 b1 <= b

证明:

从x 到 1枚举过去,对于某个i

如果 a >= i, 那么这个i放在第一天

如果a < i,那么后面肯定会遇到一个a把第一天填满(因为我们是从大到小枚举的)

所以第一天可以填满,那么除了第一天剩下的加起来也小于等于b

证毕

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head vector<int> ans1, ans2;
int main() {
fio;
int a, b;
cin >> a >> b;
int x;
for(x = ; 1LL*x*(x+)/ <= a+b; x++);
x--;
for ( ; x >= ; x--) {
if(a >= x) a -= x, ans1.pb(x);
else if(b >= x) b -= x, ans2.pb(x);
}
cout << (int) ans1.size() << endl;
for (int v : ans1) cout << v << " ";
cout << endl;
cout << (int) ans2.size() << endl;
for (int v : ans2) cout << v << " ";
cout << endl;
return ;
}
上一篇:spring controller 获取context


下一篇:扩展webservice