ZISUOJ 2024算法基础公选课练习一（3）

前言、

接（2）后完成I-J两道题

一、题目总览

二、具体题目

2.1 问题 I: 帆帆的图：

思路：

考察拓扑排序和图论（拓扑排序也是排序，<滑稽>），都是模板，我就直接拿去年ACM的拓扑排序的模板套了

参考代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5+5;
int n,m;
int val[N],in[N],dp[N][30];
int sum;
int ans;
vector<int> E[N];
queue<int> Q;
void solve(){cin >> n >> m;for(int i = 1;i<=n;i++){char c;cin >> c;val[i]=c-'a'+1;dp[i][val[i]]++;}for(int i = 1;i<=m;i++){int x,y;cin >> x >> y;E[x].push_back(y);in[y]++;}for(int i = 1;i<=n;i++){if(!in[i]) Q.push(i);}while(!Q.empty()){int x=Q.front();Q.pop();in[x]=-1;sum++;for(int i = 0;i<E[x].size();i++){int y=E[x][i];for(int j = 1;j<=26;j++){if(val[y]==j){dp[y][j]=max(dp[y][j],dp[x][j]+1);}else{dp[y][j]=max(dp[y][j],dp[x][j]);}}in[y]--;if(!in[y]){Q.push(y);}}}if(sum<n){cout << "-1" << '\n';return;}for(int i = 1;i<=n;i++){for(int j = 1;j<=26;j++){ans=max(dp[i][j],ans);}}cout << ans << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;while(_--){solve();}return 0;
}

2.2 问题 J: 帆帆打怪：

思路：

贪心的思路，先对l、r、c分别升序排序，在满足r大于l的前提下，找最小的差值d=r-l，由于找到一个d，就会少一对l和r，假设我们对l做循环，那么就需要一直对r中大于l的数据做排序，我这里把r直接放在set中，让其自动排序，这样set中第一个数据（值最小的在第一个）就是我们要找的，最后再对d排序，然后与求sigma(di*ci)即可

参考代码：

#include <bits/stdc++.h>using i64 = long long;void solve(){std::vector<i64> l,r,c;int n;std::cin >> n;l.resize(n+1);r.resize(n+1);c.resize(n+1);for(int i = 1;i<=n;i++){std::cin >> l[i];}for(int i = 1;i<=n;i++){std::cin >> r[i];}for(int i = 1;i<=n;i++){std::cin >> c[i];}std::sort(l.begin()+1,l.end());std::sort(r.begin()+1,r.end());std::sort(c.begin()+1,c.end());std::vector<i64> d(n+1,0);std::set<i64> st;int k = n;for(int i = n;i>=1;i--){while(k>=1&&r[k]>l[i]){st.insert(r[k]);k--;}d[i] = *st.begin()-l[i];st.erase(st.begin());}std::sort(d.begin()+1,d.end());i64 ans = 0;for(int i = 1;i<=n;i++) ans+=d[i]*c[n-i+1];std::cout << ans << '\n';}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;std::cin >> t;while(t--){solve();}return 0;
}