第一个案例的第二个查询

按照这个思路去编程即可。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 100005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

ll arr[MAXN];
ll num[MAXN];  // 区间差值
ll sum[MAXN] = {0};  // 差值求和

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);  // 对输入排序
    for (int i = 0; i < n - 1; ++i)
    {
        num[i] = arr[i + 1] - arr[i];
    }
    sort(num, num + n - 1);  // 对差值排序
    for (int i = 0; i < n - 1; ++i)
    {
        // 对排序后的差值求和，方便后续直接取值
        if (i)
            sum[i] = sum[i - 1] + num[i];
        else
            sum[i] = num[i];
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; ++i)
    {
        ll l, r;
        cin >> l >> r;
        ll t = r - l + 1;
        // 找到分界的位置，在这个位置之前都是小于r-l+1的
        int ind = upper_bound(num, num + n - 1, t) - num;
        // 由于使用的upper_bound，所以分别处理分界位置ind为0
        // 和ind为n-1(求差值后只剩n-1个数且从0开始，所以n-1为所有区间长度都小于r-l+1)的情况
        ll ans = 0;
        if (ind < n - 1)
        {
            if(ind)
            {
                // 通常情况
                ind--;
                ans = sum[ind] + (n - 1 - ind) * t;
            } else
            {
                ans = n*t;
            }
        }
        else
            ans = t + sum[n-2];
        cout << ans << endl;

    }

#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

E. Pavel and Triangles

题意

给定n种长度的棍子，接下来的n个整数，第i个整数表示长度为2ⁱ的棍子有多少个。
求出使用这些木棍最多能构成多少个三角形。
每个木棍都只能使用一次，且不可折断。

关键词

贪心

思路

对于当前长度的棍子，优先考虑使用两根当前长度的加一根较短的棍子去构成等腰三角形。无法构成等腰三角形时，再考虑使用三根当前长度的棍子去构成等边三角形。剩下的留给后面构造等腰三角形用。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int n;
    cin >> n;
    ll r = 0; // The remainder
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ll t;
        cin >> t;
        ll t2 = min(t / 2, r);
        t -= t2 * 2;
        r -= t2;
        ans += t2;
        ans += t/3;
        r += t%3;
    }
    cout << ans << endl;
#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}

G. Get Ready for the Battle

题意

给定n个士兵，可以划分到m个组中，其中有些组可以为空。
再给定m组个敌人，每组敌人生命值为输入的该组人数。
每一轮可以选择自己的士兵去攻击敌人，每个组在每一轮中只可以攻击一次，但可以多个组攻击同一组敌人。每一组的攻击可以造成相当于组中人数的伤害，敌人生命值为零时，这个组就算被击败了（下一轮就不能再攻击这个组了）。
并且自己的士兵分组都不会受到伤害（也就是只有我们打敌人）。
问最少需要多少轮才能将敌人全部击败。
需要输出自己士兵的分组情况和每一轮攻击的安排。

关键词

构造、排序

思路

对敌人的生命值累加求和，并且将前 i 项之和对n求余并保存在一个数组中。将对这个数组最后一项修改为n，然后排序后求差值。这个数组即为己方士兵的分组情况。按照这个分组，依照敌人输入的次序一轮一轮去杀敌即可。

• 最优解法：

  1. 假设和已知前提：用 hp_i 表示第i个敌人的生命值，k_i 表示第i个敌人在生命值低于n时的生命值（可能是攻击后的结果，也可能是初始值）,sum表示敌人生命之和。我方士兵一轮攻击最高伤害为n。
  2. 攻击策略：从第一个敌人开始（i=1），在hp_i 高于n的时候，显然，这一轮攻击无法击败这个敌人，需要所有伤害都打到它身上；在生命值小于n的时候，即生命值为k_i的时候，最好的情况就是我方士兵存在一个伤害恰好为k_i的组合，其他的士兵开始针对下一个敌人展开攻击，这样就不会在这个一轮攻击中可以击败的敌人身上浪费伤害，尽可能提高了攻击的效率。当然，在面对最后一个敌人的时候，就不需要考虑这么多了。
  3. 结论：在最优的攻击策略下，每一轮都能打满n的伤害，所以需要攻击的轮数就是对sum/n向上取整。满足最优的攻击策略只需要对于前m-1组敌人中的每一个k_i，在我方士兵的分组中都能找到一个满足的组合即可。
  4. 求解：
     

• 补充解释：

  1. 累加求余：求出上面定义的k_i。因为是对累加求余，所以处理了在某一轮攻击中，按照上述的攻击策略将前面的敌人击败后，还攻击了第i个敌人使其生命值低于n的这种情况对k_i影响。
     可以更形象地理解为，配合后面一步的排序将超过一轮攻击的情况合并到一轮攻击中来。
  2. 排序：让我们通过k_i求出我们需要的分组方案。按照上面的策略，我们只需要知道一共有多少种k_i需要我们去考虑，具体出现的位置并不会影响最终的答案，因为我们的策略就是只考虑如何能让我们的士兵分组组合出k_i来。
     对接下来下一步相减求差值的理解：对于排序后的k_i，i为1时，是最少一种敌人情况，直接按照这个分组即可；i>1时（可以拿i=2代入），说明前面的k_i-1已经考虑过，只需要考虑从k_i-1的组合增加一个小的分组使其得到k_i即可，这个小的分组的人数就是k_i-k_i-1了。
  3. 末项为n：显然对已排序序列的求差值后，其中各项之和一定等于最后一项。一轮攻击下来最多能造成n的伤害。这里将最后一项修改为n，就是为了保证在后面的步骤中，一轮下来最多有n点伤害。
  4. 不足补0：一共有m（7）个分组，且题意说明了可以存在空的组，没有分配士兵的组就是0。

代码

#include <bits/stdc++.h>
#define Debug 0
#define MAXN 1000005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int hp[MAXN] = {0};
int b[MAXN] = {0};
ll sum = 0;
int main ()
{
#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &hp[i]);
        sum += hp[i];
        b[i] = sum % n;
    }
    b[m] = n;
    sort(b + 1, b + 1 + m);
    for (int i = m; i >= 0; --i)
    {
        b[i] = b[i] - b[i - 1];
    }
    printf("%lld\n", (sum - 1) / n + 1);

    for (int i = 1; i <= m; ++i)
    {
        printf("%d%c", b[i], (i==m?'\n':' '));
    }

    int cur = 1; // Evlampy's army group
    for (int i = 1; i <= m; ++i)
    {
        // The enemy currently under attack
        int t = hp[i];
        while (t > 0)
        {
            t -= b[cur];
            ++cur;
            printf("%d%c", i, (cur>m?'\n':' '));
            if (cur > m)
            {
                cur = 1;
            }
        }
    }
    while (cur > 1 && cur <= m)
    {
        cout << 1 << (cur == m ? "\n" : " ");
        cur++;
    }
#ifdef FILE_IN
    fclose(stdin);
#endif
    return 0;
}

留坑

F. Niyaz and Small Degrees

题意

关键词

思路

代码

H. Triple

题意

关键词

思路

代码