洛谷 8 月月赛

第一次打月赛，水了200
ψ(*｀ー´)ψ

T1 造房子

题目

$pigstd$ 有 $a$ 个 $A$ 材料和 $b$ 个 $B$ 材料，造第 $i$ 层楼需要 $i$ 个 $A$ 材料与 $i$ 个 $B$ 材料。
但是 $pigstd$ 觉得房子不够高，于是他拿出了 $c$ 块钱，每块钱都可以用来买 1 个 $A$ 材料或者 1 个 $B$ 材料。
现在 $pigstd$ 想知道，他最多能建多少层楼的房子。

---

输入

第一行三个整数 $a$,$b$。

---

输出

一行一个整数，表示 $pigstd$ 最多能建多少层楼的房子。

---

样例

input 1
1 2 3

output 1
2

input 2
1 2 5

output 2
2

---

说明/提示

【样例 1 说明】
$pigstd$ 买 2 个 $A$ 材料和 1 个 $B$ 材料后就有 3 个 $A$ 材料和 3 个 $B$ 材料，最多可以建 2 层楼的房子。
（花费 1+2 个 $A$ 材料和 1+2 个 $B$ 材料）

【样例 2 说明】
$pigstd$ 买 3 个 $A$ 材料后就有 4 个 $A$ 材料和 5 个 $B$ 材料，最多可以建 2 层楼的房子。
（花费 1+2 个 $A$ 材料和 1+2 个 $B$ 材料）

【数据规模与约定】
对于 100% 的数据，0≤$a$,$b$,$c$≤10^12。

---

解题思路

预处理
先将$A$材料和$B$材料的个数差的差距变小
如果$c$还有剩余，平分给$A$材料和$B$材料

二分答案
二分可以建到第几层
用高斯定理求出一共要用的材料
最后输出左边界

---

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long a,b,c,n,l,r; 
double x;
int main()
{scanf("%lld%lld%lld",&a,&b,&c);if (a>b)swap(a,b);  //小的给A材料if (a<b)  //等于就不用补差了if (c+a>=b){c=c-(b-a);a=b;} else {a+=c; c=0;}a+=c/2,b+=c/2; //c平分给A和Bl=1,r=2000000;  //定边界while (l<r){  long long mid=(l+r+1)/2;x=(mid+1)*(mid*1.0/2);  //高斯定理求材料数if (x>a)  //不够往左靠，有剩往右靠r=mid-1;else l=mid;}printf("%lld\n",l);return 0;
} 

T2 排列

题目

$pigstd$ 有一堆数，他想在这么多数中选出若干个数排成一列，记为 $x$ 1,$x$ 2,⋯ ,$xp$（$p$ 为数的个数）。
这一列数合法当且仅当满足以下条件：

• $p$≥2。
• 令 $yi$=$x$（$i$+1）−$xi$​（特别的，$yp$=$x$ 1−$xp$），如果把 $y$ 1 到 $yp$ 按 $y$ 1,$y$ 2,⋯ ,$yp$​ 的顺序排成一圈，那么每两个相邻的数互为相反数且绝对值都为 $k$。

$pigstd$ 想知道，在所有合法的数列中，所有在这个数列中的数之和最大是多少。

---

输入

第一行两个整数 $n$,$k$。
接下来 $n$ 行，每行两个整数 $ai$,$bi$​，表示 $pigstd$ 有 $bi$​ 个 $ai$​。
不保证 ai​ 互不相同，若有 ai 相同则累加其个数计算。

---

输出

一行一个整数，表示在每一种排列中，所有在这个排列中的数的最大的和。
若没有合法的排列，则只输出 NO。

---

样例

input
4 3
1 5
2 4
3 3
0 2

output
6

---

说明/提示

【样例 1 说明】
当 $pigstd$ 的排列为：0,3,0,3 或 3,0,3,0 时，总和最大，为 6。

【数据规模与约定】
对于 100% 的数据，1≤$n$≤10 ^ 6，0≤$k$,$ai$≤10 ^ 6，1≤$bi$≤10 ^ 6。

本题采用捆绑测试。

• $Subtask$ 1（5 $points$）：保证无合法的数列；
• $Subtask$ 2（15 $points$）：$k$=0；
• $Subtask$ 3（5 $points$）：$n$=1；
• $Subtask$ 4（5 $points$）：$n$=2；
• $Subtask$ 5（30 $points$）：$n$,$k$,$ai$,$bi$≤10^3；
• $Subtask$ 6（40 $points$）：无特殊限制。

---

解题思路

我们可以从样例解释中看出
数列一定是$x$,$y$,$x$,$y$,$x$,$y$…$x$,$y$的
并且一定是偶数个的（题目中特别解释，第一个数和最后一个数的差也要满足$k$，除非$k$=0，否则$x$！=$y$）
我们可以枚举$x$
$y$=$x$+$k$，如果$y$存在，我们就可以构造一个数列

• $k$ == 0时，$x$ == y，所以要特判$x$的个数必须大于2（$p$≥2），$x$*$a$[$x$]和当前的最优答案比较
• $k$>0时，取$x$和$y$的个数中的较小值和（$x$+$y$）相乘与当前最优答案比较

---

代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,k,x,y,ma,c,p,a[1000020];
long long ans;
int main()
{scanf("%lld%lld",&n,&k);for (int i=1;i<=n;i++){scanf("%lld%lld",&x,&y);ma=max(x,ma);a[x]+=y;  //累加个数}for (int i=0;i<=ma-k;i++)if (a[i]!=0 && a[i+k]!=0)  //保证x和y都有{   if (k!=0)  //分类讨论{ p=1;c=min(a[i],a[i+k]);  //取个数中的较小值long long x=(i+i+k)*c;  //求和ans=max(ans,x);  //更新答案}else if (a[i]>1)  //特判个数{p=1;long long x=i*a[i];  //求和ans=max(ans,x);  //更新答案}}if (p)  //能构造出合法数列printf("%lld\n",ans);else printf("NO");return 0;
}