S08577 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-02 15:30:48
一开始看到这道题的时候，就想到用tarjan，求桥数。 但是我想到了用并查集来求（hb说可以用并查集做，当然选简单的）。 我们枚举每一个边 $i$，设这条边 $i$ 为断点，再枚举 $j$（$j \ne i$)，将 $x_j$ 和 $y_j$ 联通。第一个循环最后，判断 $x_i $ 和 $y_i$ 是否在一个集合里。
for(int i=1;i<=m;i++){
init();\/\/并查集初始化
for(int j=1;j<=m;j++) if(j!=i) fa[findf(x[j])]=findf(y[j]);
if(findf(x[i])!=findf(y[i])) cnt++;\/\/桥数加一
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-09 14:29:06
打眼一看，这道题要求最多能干多少工作，肯定是贪心。
知道这个就好做了，我们思考如何才能最优，我们将输入 开始时间和结束时间的数组 按照结束时间从小到大排列，显然是最优的。
定义一个变量 $time$ 代表现在是什么时刻。
如果 $time$ 加上起始时间比结束时间要小，就说明这个任务可以完成，$time$ 加上开始时间，并将开始时间压入优先队列。
否则，在优先队列不空的前提下，我们选一个之前做过的任务用时最长的和现在的比较，如果现在的用时短，就把用时最长的扔掉，$time$ 先减去用时最长的开始时间再加上现在的开始时间。将现在的开始时间压入优先队列。
最后输出优先队列里面有几项即可。
#include<iostream>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
const int N=4e6+5;
const int INF=1e9;
struct customer{
int st,fi;\/\/start,finish
}c[N];
int n;
bool cmp(customer x,customer y){
return x.fi<y.fi;
}
signed main(){
int T;
cin>>T;
while(T--){
priority_queue<int> q;
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i].st>>c[i].fi;
}
int time=0;
sort(c+1,c+1+n,cmp);
for(int i=1;i<=n;i++){
if(time+c[i].st<=c[i].fi){\/\/如果时间加上起始时间比这个任务结束时间要早
time+=(c[i].st);\/\/时间加上任务的时间
q.push(c[i].st);\/\/进入优先队列
}
else{
if(!q.empty()){
int d=q.top();
if(d>c[i].st){\/\/如果这个任务比做过的任务中最大的用时要短
time-=d;
time+=c[i].st;\/\/换掉任务，以求最优
q.pop();
q.push(c[i].st);
}
}
}
}
cout<<q.size()<<endl;
if(T) cout<<endl;
}
}
\/*
2
6
7 15
8 20
6 8
4 9
3 21
5 22
6
7 15
8 20
6 8
4 9
3 21
5 22
*\/
\/*
2
6
7 15
8 20
6 8
4 9
3 21
5 22
6
7 15
8 20
6 8
4 9
3 21
5 22
*\/
\/*
1
6
7 15
8 20
6 8
4 9
3 21
5 22
*\/
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-14 19:45:05
我们一看插入和删除就知道用链表，可是现在几乎没有人用链表 （我忘了） ，于是我就用数组模拟指针，定义 $l$ 数组存这个数左边是哪个数，$r$ 数组存这个数右边是哪个数。
初始化不必多说，就在最后用 $r$ 数组存上 $-1145$。
根据链表的原理，我们要添加一个数，就是让这个数前面后面的链改变一下，就像下图
根据此图，我们可以修改一下我们的数组。
$$l_5=1 $$ $$l_4=5 $$ $$r_1=5 $$ $$r_5=4 $$
这一部分写成代码较为困难，涉及到许多转化，自己在草稿纸上手写几遍再多看看代码就明白了。
if(op==1){
cin>>x>>y;
l[r[x]]=y;
l[y]=x;
int d=r[x];
r[l[y]]=y;
r[y]=d;
}
删除相对简单一点，我们只需要把连着要删除数字的链连上前面的或后面的。 这样说可能不清楚，可参考下图,再看看代码就能理解。
else{
cin>>x;
int L=l[x];
int R=r[x];
l[R]=l[x];
r[L]=r[x];
}
最后就是输出了，我们在 $r$ 的最后放了一个 $-1145$，就是为了输出什么时候到达终点。
int tot=0;
while(r[tot]!=-1145){
\/\/cout<<tot<<" ";
cout<<r[tot]<<" ";
tot=r[tot];
}
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const int N=2e6+5;
int a[N];
\/\/int l[N],r[N];\/\/左指针数组，右指针数组
map<int,int> l,r;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
l[a[i]]=a[i-1];
r[a[i-1]]=a[i];
}
r[a[n]]=-1145;
int T;
cin>>T;
while(T--){
int op,x,y;
cin>>op;
if(op==1){
cin>>x>>y;
l[r[x]]=y;
l[y]=x;
int d=r[x];
r[l[y]]=y;
r[y]=d;
}
else{
cin>>x;
int L=l[x];
int R=r[x];
l[R]=l[x];
r[L]=r[x];
}
}
int tot=0;
while(r[tot]!=-1145){
\/\/cout<<tot<<" ";
cout<<r[tot]<<" ";
tot=r[tot];
}
}
这道题是一道练习链表很好的题目。
鲁ICP备2025150228号