- 贪心
[NOIP 2007 普及组] 纪念品分组(思路)
- @ 2025-12-2 17:18:51
先sort排序再二分;
二分:
左端点:l;
左端点:n;
二分要先判断左端点是否小于等于右端点;
如果a[左端点]加a[右端点]是否小于等于纪念品价格之和的上限;
如果是:
{
左端点++,右端点--;统计个数的cnt++;
}
如果不是:
{
只用右端点--;但统计个数的cnt还得++;
}
最后输出cnt;
0 条评论
目前还没有评论...
先sort排序再二分;
二分:
左端点:l;
左端点:n;
二分要先判断左端点是否小于等于右端点;
如果a[左端点]加a[右端点]是否小于等于纪念品价格之和的上限;
如果是:
{
左端点++,右端点--;统计个数的cnt++;
}
如果不是:
{
只用右端点--;但统计个数的cnt还得++;
}
最后输出cnt;