课上实例1

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

using namespace std;

// 为了减少数组越界的风险,多开些空间 
const int N = 100010;

int n;
int h[N];

// e表示能量 
bool check(int e)
{
    // 递推 
    for (int i = 1; i <= n; i ++ )
    {
        e = e * 2 - h[i];
        if (e >= 1e5) return true;
        if (e < 0) return false;
    }
    // 说明e一定在0到1e5之间,返回true 
    return true;
}

int main()
{
    // 输入输出较大≥10^5,建议用scanf 
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    // 二分
    // 最开始确定答案的可能范围
    // 最小值为0
    // 最大值最多为塔的最高高度 
    int l = 0, r = 1e5;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    // 循环结束时l和r相等 
    printf("%d\n", r);

    return 0;
}

课上实例2

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2500010;

// 用一个结构体存中间状态 
struct Sum
{
    // s表示c^2 + d^2 
    int s, c, d;
    // 重载小于号,用于排序 
    bool operator< (const Sum &t)const
    {
        // 三个关键字,字典序比较
        // 先比较s,如果s不相同返回s较小者 
        if (s != t.s) return s < t.s;
        // 如果s相同比较c
        // 如果c不相同返回c较小者  
        if (c != t.c) return c < t.c;
        // 如果s和c都相同
        // 返回d较小者 
        return d < t.d;
    }
}sum[N];

// m表示所有组合的个数 
int n, m;

int main()
{
    cin >> n;

    // 按字典序枚举c和d的所有组合 
    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);

    // 枚举a和b 
    for (int a = 0; a * a <= n; a ++ )
        for (int b = 0; a * a + b * b <= n; b ++ )
        {
            // 计算差值 
            int t = n - a * a - b * b;
            // 二分
            // 找到大于等于差值的最小的一个数 
            int l = 0, r = m - 1;
            while (l < r)
            {
                int mid = l + r >> 1;
                // 如果当前位置的s≥t
                // 说明答案在该位置的左边   
                if (sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            // 最后判断l位置是否为t 
            if (sum[l].s == t)
            {
                // 是的话说明我们找到了一组解 
                printf("%d %d %d %d\n", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }

    return 0;
}

课上实例3

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

using namespace std;

const int N = 100010;

int n, k;
// h[]高度,w[]长度 
int h[N], w[N];

bool check(int mid)
{
    // res最多能分多少块 
    int res = 0;
    // 枚举每块巧克力 
    for (int i = 0; i < n; i ++ )
    {
        // 注意一定要加括号,才能保证下取整 
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k) return true;
    }

    return false;
}

int main()
{
    // 输入规模较大,推荐用scanf()
    scanf("%d%d", &n, &k);
    // 读入 
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);

    // 二分
    // 保证每个小朋友至少获得1x1
    // 最大不会超过h,w最大值 
    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);

    return 0;
}

课上实例4

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

using namespace std;

const int N = 100010;

int n, m;   // 序列长度和询问个数 
// a[]和s[]为全局数组,初值为0
// 局部数组初值是随机值 
int a[N];   // 表示原数组
int s[N];   // 表示前缀和数组

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ )
    {
        // 将n个数读入
        scanf("%d", &a[i]);
        // 前缀和 
        s[i] = s[i - 1] + a[i];
    }

    // 处理m个询问 
    while (m -- )
    {
        // 区间范围[l, r] 
        int l, r;
        scanf("%d%d", &l, &r);
        // 边界问题:当l = 1时,即a[1]到a[r] 
        // 相当于s[r] - s[0]
        // s[0] = 0 
        // 只要前缀和下标从1开始,且s[0] = 0就没有问题
        // 否则要加一个特判 
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

课上实例5

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

using namespace std;

// 本题读入量大,建议用scanf()读入 
const int N = 1010;

int n, m, q;
// 原数组a[],前缀和数组s[]
// 同时每个元素最大为1000
// 因此前缀和最大为1000*1000*1000
// 不会超过int范围 
int a[N][N], s[N][N];

int main()
{
    // n为矩阵行数
    // m为矩阵列数
    // q为询问个数 
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            // 读入元素 
            scanf("%d", &a[i][j]);
            // 同时计算前缀和矩阵 
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }

    // 处理q个询问 
    while (q -- )
    {
        // 子矩阵左上角坐标(x1, y1)
        // 子矩阵右下角坐标(x2, y2)  
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }

    return 0;
}