创建个人网站的流程,手机管理网站模板下载软件,seo店铺描述,旅游网站建设答辩ppt第十五届
CA组省赛 AcWing5980.训练士兵 方法一#xff1a;树状数组:O(nlogn) self-complete
/*先枚举组团#xff0c;后分析每个士兵#xff0c;有一个特点#xff0c;组团费用是固定的#xff0c;那当然是让所有士兵一块训练#xff0c;训练完的士兵也不会有损失当还…第十五届
CA组省赛 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;
}
