天津商城网站设计公司游戏代理

第十五届

C++A组省赛

AcWing5980.训练士兵

方法一：树状数组:O(nlogn)

• self-complete

/*先枚举组团，后分析每个士兵，有一个特点，组团费用是固定的，那当然是让所有士兵一块训练，训练完的士兵也不会有损失当还需要升级的士兵的金币之和小于组团时就各自训练，此时花费也已经固定了首先将经验按照从大到小排序，这样每次组团训练，会从后向前减少不需要训练的士兵，这样就能利用前缀和来判断是否需要单独训练每次组团先训练完一整类需要经验值相同的士兵再判断, 由于会对一整个区间进行修改求和，使用树状数组时间复杂度O(n)
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long longusing namespace std;const int N = 100010;struct Soldier{int coin, ep;bool operator< (const Soldier o) const{return ep > o.ep;}
}sl[N];int sc[N], tr[N];
int n, S;int lowbit(int x){return x & -x;
}void add(int x, int c){for (int i = x; i < N; i += lowbit(i))tr[i] += c;
}int sum(int x){int s = 0;for (int i = x; i; i -= lowbit(i))s += tr[i];return s;
}signed main(){scanf("%lld%lld", &n, &S);for (int i = 1; i <= n; i ++){scanf("%lld%lld", &sl[i].coin, &sl[i].ep);}sort(sl + 1, sl + n + 1);for (int i = 1; i <= n; i ++){sc[i] = sc[i - 1] + sl[i].coin;add(i, sl[i].ep - sl[i - 1].ep);}int res = 0;for (int i = n; i; i --){int cep = sum(i);if (cep > 0){if (sc[i] >= S){add(1, -cep);add(i, cep);res += S * cep;}else{res += sl[i].coin * cep;} }}printf("%lld\n", res);return 0;
}

方法二：哈希+整体操作（挖掘性质): O(n)

• 😦

/*由于组团训练肯定是所有士兵一起参加更好，所以可以把过程分为两种情况，一种是所有士兵组团训练，一种是所有士兵单独训练，而哪些已经训练完成的士兵就不用管了每次比较是组团和单独训练的花费金额来判断选用哪种情况
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long longusing namespace std;const int N = 100010;int c[N], p[N];
int n, S;
int a[N * 100]; // a[k]哈希表，表示经过k轮后，完成训练后对应士兵的花费signed main(){scanf("%lld%lld", &n, &S);int maxt = 0;//一共只需要升maxt次所有士兵就能升满级int i_S = 0;//表示单独训练花费for (int i = 1; i <= n; i ++){scanf("%lld%lld", &c[i], &p[i]);maxt = max(maxt, p[i]);i_S += c[i];a[p[i]] += c[i];//训练多少轮后到达满级，此时对应的i_s将其去掉，未到满级是a[i]为0}int res = 0;for (int i = 1; i <= maxt; i ++){if (S < i_S){res += S;}else{res += i_S;}i_S -= a[i];}printf("%lld\n", res);return 0;
}