Codeforces Round #517 (Div. 2)(1~n的分配)
2024-09-03 23:45:52
题:https://codeforces.com/contest/1072/problem/C
思路:首先找到最大的x,使得x*(x+1)/2 <= a+b
那么一定存在一种分割使得 a1 <= a 且 b1 <= b
证明:
从x 到 1枚举过去,对于某个i
如果 a >= i, 那么这个i放在第一天
如果a < i,那么后面肯定会遇到一个a把第一天填满(因为我们是从大到小枚举的)
所以第一天可以填满,那么除了第一天剩下的加起来也小于等于b
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int M=1e6+;
int book[M];
int main(){
ll n,m;
cin>>n>>m;
ll i=;
while((i+)*i<=(n+m)*)
i++;
i--;
int tot=;
for(int j=i;j>=;j--){ if(n>=j){ book[j]=;
n-=j;
tot++;
}
if(n==)
break;
}
cout<<tot<<endl;
for(int j=;j<=i;j++){
if(book[j])
cout<<j<<' ';
}
cout<<endl;
cout<<i-tot<<endl;
for(int j=;j<=i;j++)
if(!book[j])
cout<<j<<' ';
}
最新文章
- Verilog学习笔记简单功能实现(七)...............接口设计(并行输入串行输出)
- 面向.Net程序员的前端优化
- for循环计数
- du 命令,对文件和目录磁盘使用的空间的查看
- kafka监控之KafkaOffsetMonitor
- HTML表单样式
- Bootstrap迁移系列 - Navbar
- ExtJS练手
- Ural 1519. Formula 1 优美的插头DP
- sql问题
- 【m从翻译os文章】写日志禁令Sqlnet.log和Listener.log
- 一起学习android图片四舍五入图片集资源 (28)
- 4063: [Cerc2012]Darts
- LOJ #6041. 事情的相似度
- ubuntu16.04 pip install scrapy 报错处理
- sed:-e 表达式 #1,字符 10:未终止的“s”命令
- js滚动条如何缓慢的回到顶部?
- canvas 实现弹跳效果
- Access-Control-Allow-Origin与跨域
- maven 生命周期、生命周期阶段、插件、目标