算法刷题系列：二分（一）

这个算法竞赛就是个记忆大赛，你做不出来的题说明你没做过同类型或者同个模型的题，当然不是你的智商有问题，所以多做题很重要，加油！

一、糖果促销

码题集：糖果促销

第一种当然是自己最开始想到的，那么就是这个你买多少糖，那么你能最后通过换取最终得到的糖也就多，这显然是单调的，所以我想到了二分，然后就是判断在满足条件下，最小的那一个就行了，然后就套模板，写个check就行了，值得注意的是，当p为1时，check里会无限循环，所以得特判一下。
当然也可以直接用数学思维 k -= (k-1) / p，这当然我是想不到，反正这个算法竞赛就是个记忆大赛，你做不出来的题说明你没做过同类型或者同个模型的题，当然不是你的智商有问题，加油！

#include <cstdio>
#include <iostream>

using namespace std;
int T, p, k;

bool check(int v)
{
    int res = v;
    while(v / p)
    {
        res += v / p;
        v = v % p + v / p;
    }

    return res >= k;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &p, &k);
        if(p == 1)
        {
            printf("%d\n", (bool)k);
            continue;
        }

        int l = 0, r = k;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", l);
    }
}

二、四平方和

题目描述：
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5=0^2+0^2+1^2+2^2
7=1^2+1^2+1^2+2^2
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：0≤a≤b≤c≤d并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5?10^6

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e6+10;

struct Sum
{
    int S, c, d;
    bool operator<(const Sum& other)
    {
        if(S != other.S) return S < other.S;
        if(c != other.c) return c < other.c;
        return d < other.d;
    }
}Sum[N];

int n,m;

int main()
{
    scanf("%d", &n);
    for(int c = 0; c * c <= n; c++)
    {
        for(int d = c; c * c + d * d <= n; d++)
        {
            Sum[m++] = {c*c+d*d,c,d};
        }
    }
    
    sort(Sum,Sum+m);
    for(int a = 0; a * a <= n; ++a)
    {
        for(int b = a; a * a + b * b <= n; ++b)
        {
            int sum = n - a * a - b * b;
            int l = 0, r = m - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(Sum[mid].S >= n) r = mid;
                else l = mid + 1;
            }
            if(Sum[l].S == sum)
            {
                printf("%d %d %d %d", a, b, Sum[l].c, Sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}