题目地址：CF1091E New Year and the Acquaintance Estimation

首先，易知 \(ans\) 的奇偶性与所有给出的数的和的奇偶性相同

其次，易证 \(ans\) 的取值为一段连续的奇偶性相同的数，因此只需要到一个上界和下界（或者判断出无解输出 \(-1\) ）

接下来的问题就是怎么判断一个状态合不合法以及如果不合法需要加还是减

题目中给出了一个Wiki的链接：Graph realization problem

链接中给出了问题的解法：Erdős–Gallai theorem

Erdős–Gallai定理的基本内容为：

一个非负整数序列 \(d_1≥d_2≥\cdots≥d_n\) 可以表示为 \(n\) 个顶点的简单图度序列，当且仅当 \(\sum_{i=1}^{n}\ d_i\) 为偶数且对每个 \(k\in [1,n]\) 满足

\[\sum_{i=1}^{k}\ d_i ≤ k(k-1)+\sum_{i=k+1}^{n}\ min(d_i,k)\]

对这个公式的理解 伪证 ： \(1\) ~ \(k\) 这 \(k\) 个点的度数和最大为——所有点之间两两连线产生的度数和，加上剩下每个点可连线数量的最大值，这保证了公式的必要性；而非严格单调递减则保证了公式的充分性

利用公式朴素判断一次需要 \(O(n^2)\) ，但是可以优化到 \(O(n)\) ，外层嵌套两个二分，这样可以在 \(O(n\ log\ n)\) 的时间复杂度内解决问题

上代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500006;
int n, a[N], c[N], cc[N], ansl = -1, ansr = -1;

int pd(int x) {
    memcpy(cc, c, sizeof(cc));
    ++cc[x];
    int w = 0, t = 0;
    ll s = 0, k = 0;
    for (int i = 0; i <= n; i++) {
        int num = (i == t && (t == n || a[t] < x)) ? x : a[t++];
        s += num;
        --cc[num];
        k += n - i - (w += cc[i]) - min(num, i);
        if (s > k + (ll)i * (i + 1)) return (i == t) ? 1 : -1;
    }
    return 0;
}

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    cin >> n;
    ll s = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        s += a[i];
        ++c[a[i]];
    }
    s &= 1;
    sort(a, a + n, cmp);
    int l = 0, r = (n - s) >> 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (pd((mid << 1) + s) == -1) l = mid + 1;
        else {
            ansl = mid;
            r = mid - 1;
        }
    }
    l = ansl;
    r = (n - s) >> 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (pd((mid << 1) + s) == 1) r = mid - 1;
        else {
            ansr = mid;
            l = mid + 1;
        }
    }
    if (ansl == -1 || ansr == -1) puts("-1");
    else for (int i = ansl; i <= ansr; i++)
            printf("%lld ", (i << 1) + s);
    return 0;
}

另外线段树也可以优化，这样时间复杂度会多一个 \(log\) ，对 \(500000\) 的数据来说有些吃力，就不码了

最新文章

1. android-async-http AsyncHttpClient介绍
2. ThinkPHP 表单提交操作成功后执行JS操作如何刷新父页面或关闭当前页等操作
3. ITextSharp导出PDF表格和图片（C#）
4. c#链接数据库
5. p++ ++p
6. SPOJ #442 Searching the Graph
7. 在Mac OS X中使用VIM开发STM32（3）
8. CSharp Algorithm - How to traverse binary tree by breadth (Part II)
9. COJN 0583 800602分苹果
10. jdk配置环境变量
11. app耗电优化之四 使用AlarmManager对任务进行合理安排
12. TurnipBit口袋编程计算机：和孩子一起DIY许愿的流星
13. 关于“应用程序无法启动，因为应用程序的并行配置不正确。请参阅应用程序事件日志，或使用命令行sxstrace.exe工具”问题的解决方法
14. time、datetime、calendar
15. 关于读取excel 和 写excel
16. SpringBoot+Mybatis配置Pagehelper分页插件实现自动分页
17. Visual Studio Team Services 动手实验
18. Visual Studio 2012 Update 1 离线升级包（相当于VS2012 SP1离线补丁包）
19. word2013怎样批量重设图片和大小？（转）
20. 【PHP代码审计】 那些年我们一起挖掘SQL注入 - 1.什么都没过滤的入门情况

热门文章

1. GD32 ------ 使用外部中断，中断函数需要延时才能读到真正电平
2. BZOJ3531 树剖 + 动态开点线段树
3. SQL语法基础之INSEART语句
4. Windows Dll Injection、Process Injection、API Hook、DLL后门/恶意程序入侵技术
5. HDU 1006(时钟指针转角 **)
6. Arrays.asList() 的使用注意
7. 简述react与vue的区别
8. npm与nrm
9. 解决浏览器跨域限制方案之WebSocket
10. 修改xshell的默认字间距和行间距