1、因为要在能击败所有敌军的基础下,求存活最多的数量,那么我们可以对敌军的防御力从大到小排列,对于友军的攻击力从大到小排列,这样遍历一次敌军,将所有可以击败该敌军的友军防御力存入multiset,因为防御力可能会重复
2、对于多个可以击败敌军的友军,我们挑选那个刚刚好可以击败敌军且存活的,如果没有,那么横竖都为失去一个友军,干脆失去那个防御力最低的
3、对于存活的计算,我们再选择友军时,可能所有的友军不会都加入set中,因此最后要加上,同样的set里的所有元素不一定都会上场,也得加上
- # include
- # include
- # include
- # include
- using namespace std;
- const int N = 100000+10;
- int t, n, m;
- multiset<int>s;
- struct fri{
- int g, f;
- }f[N];
- struct di{
- int g, f;
- }d[N];
- bool cmp1(fri f1, fri f2)
- {
- return f1.g>f2.g;
- }
- bool cmp2(di d1, di d2)
- {
- return d1.f>d2.f;
- }
- int main()
- {
- cin>>t;
- for (int k=1; k<=t; k++)
- {
- s.clear();
- cin>>n>>m;
- for (int i=1; i<=n; i++)
- {
- cin>>f[i].g>>f[i].f;
- }
-
- for (int i=1; i<=m; i++)
- cin>>d[i].g>>d[i].f;
- sort(f+1, f+1+n, cmp1);
- sort(d+1, d+1+m, cmp2);
- int pos = 1, ans = 0, flag = 0;
- for (int i=1; i<=m; i++)
- {
- while (f[pos].g>=d[i].f && pos<=n)
- {
- // cout<
- s.insert(f[pos].f);
- pos++;
- }
- if (s.size()==0)
- {
- flag = 1;
- cout<<"Case #"<
": -1"< - break;
- }
- auto it = s.upper_bound(d[i].g);
- if (it!=s.end())
- {
- ans++;
- s.erase(it);
- }
- else
- {
- s.erase(s.begin());
- }
- // cout<
- }
- // cout<
- if (!flag)
- cout<<"Case #"<
": "<size()+n+1-pos< - }
-
-
- return 0;
- }
NC23803 DongDong认亲戚
题目链接
关键点:
1、利用map来使名字对应数字,然后直接上并查集
完整代码
- # include
- # include
- # include
- using namespace std;
- const int N = 200000+10;
- int n, m;
- int fa[N];
- map
int>mp; - int find(int x)
- {
- return (x==fa[x])? x: fa[x] = find(fa[x]);
- }
- void unite(int x, int y)
- {
- fa[find(x)] = find(y);
- }
- int main()
- {
- for (int i=0; i
- fa[i] = i;
- cin>>n>>m;
- for (int i=1; i<=n; i++)
- {
- string s;
- cin>>s;
- mp[s] = i;
- }
- for (int i=1; i<=m; i++)
- {
- int x;
- string a, b;
- cin>>x>>a>>b;
- if (x==2)
- {
- int f1 = find(mp[a]), f2 = find(mp[b]);
- if (f1==f2)
- cout<<"1"<
- else
- cout<<"0"<
- }
- else
- unite(mp[a], mp[b]);
- }
-
-
- return 0;
- }
NC235622 叠积木
题目链接
关键点:
1、我们用一个fa数组存每个积木的父亲(设为该积木的最底下的积木),一个d数组存每个积木到最底下有多少个积木,一个cnt数组存该积木一共有多少(下标为最底下的积木)
2、对于每一次的搭建,比如从x->y,先找到x的父亲fx,y的父亲fy,判断不相等后将
fa[fx] = fy,d[fx] = cnt[fy](当前x父亲(即x最底下的积木距离此时的父亲结点(fy)的距离为y积木的数量)), cnt[fy]+=cnt[fx](y积木的数量加上x积木的数量)
3、对于find,除了fa[x] = find(fa[x]);还有d[x] += d[fa[x]],不断更新该积木与父亲的距离
完整代码
- # include
- # include
- using namespace std;
- const int N = 30000+10;
- int n;
- int fa[N], d[N], cnt[N];
- int find(int x)
- {
- if (fa[x]!=x)
- {
- int t = find(fa[x]);
- d[x] += d[fa[x]];
- fa[x] = t;
- }
- return fa[x];
- }
- void unite(int x, int y)
- {
- int f1 = find(x), f2 = find(y);
- if (f1!=f2)
- {
- fa[f1] = f2;
- d[f1] = cnt[f2];
- cnt[f2] += cnt[f1];
- }
- }
- int main()
- {
- cin>>n;
- for (int i=1; i<=N; i++)
- {
- fa[i] = i;
- d[i] = 0;
- cnt[i] = 1;
- }
- for (int i=1; i<=n; i++)
- {
- char c;
- cin>>c;
- if (c=='M')
- {
- int x, y;
- cin>>x>>y;
- unite(x, y);
- }
- else
- {
- int x;
- cin>>x;
- find(x);
- cout<
- }
- }
-
-
- return 0;
- }
-
相关阅读:
高级架构师_Docker_第2章_ Docker核心原理_ 第2节_Docker网络
【蓝桥杯软件赛 零基础备赛20周】第3周——填空题
范西特-泽尼克定理的证明
并查集快速合并
Mobile-Former: Bridging MobileNet and Transformer详解
办理河南公司名称变更成无区域名称核名条件和流程
C,C++中原生数组索引的奇怪写法
【Python算法Algorithm】专栏导读
Android并发编程与多线程
ESP32学习笔记 - 基于 ESP32 移植 LVGL8.3
-
原文地址:https://blog.csdn.net/m0_60531106/article/details/126237035
-
最新文章
-
C++11 线程同步接口std::condition_variable和std::future的简单使用
Go runtime 调度器精讲(十一):总览全局
Spring框架漏洞总结
Angular 18+ 高级教程 – 国际化 Internationalization i18n
基于Tauri2+Vue3搭建桌面端程序|tauri2+vite5多窗口|消息提醒|托盘闪烁
ComfyUI 基础教程(五) —— 应用 IP-Adapter 实现图像风格迁移
网络空间的“边水往事”?针对华语黑产及用户进行攻击的 APT-K-UN3 活动分析
伪装“黑神话悟空修改器”传播木马的活动分析
全球蓝屏后,微软决定将安全踢出Windows内核
Java读取寄存器数据的方法