题目描述
王老师的班级要开始评选三好学生啦，最后要评选两个人出来。
王老师班级一共有 n 个学生，编号分别为 1,2,…,n，每个人把自己心中的两名最佳三好学生 a 和 b 告诉 王老师。
- 可能存在两个人，他们心中的两名最佳三好学生是相同的。例如样例 1 所示。
现在 王老师 要选出两个人，为了让学生们满意，至少需要 m 个人同意最后的决定。所谓同意指的是，某班级学生同意这最终名单，当且仅当该学生心中的两名最佳三好学生至少有一个出现在最终名单里。
请你帮 王老师 算算，有多少种可能的组合（与选出来的人的顺序无关），符合条件
数据范围
对于 60% 的数据，n 的范围 [3,104];
对于 100% 的数据，n 的范围 [3,105], m 的范围 [0,n]，并且保证 a=b,1≤a,b≤n
根据题目可知，我们可以用一个后缀数组s来维护其间重复的人同意数，则我们可以枚举i，找到最小的答案，则在它后面的所有值便都是答案，最后/2去掉重复条件即可。
代码：
#include <bits/stdc++.h>using namespace std;
#define int long long
int a,b,d[100005],cnt[100005],s[100005],num[100005],vis[100005],n,m,ans;
vector<int>g[100005];
signed main(){
freopen("vote.in","r",stdin);
freopen("vote.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a>>b;
d[a]++,d[b]++;
g[a].push_back(b),g[b].push_back(a);
}
for(int i=1;i<=n;i++)++cnt[d[i]];
for(int i=n;i>=0;i--)s[i]=s[i+1]+cnt[i];
for(int i=1;i<=n;i++){
int de=m-d[i];
if(de<=0)ans+=n-1;
else {
int tmp=s[de];
if(d[i]>=de)tmp--;
for(int j=0;j<g[i].size();j++)num[g[i][j]]=vis[g[i][j]]=0;
for(int j=0;j<g[i].size();j++)num[g[i][j]]++;
for(int j=0;j<g[i].size();j++){
int v=g[i][j];
if(vis[v])continue;
vis[v]=1;
if(d[v]>=de && d[v]-num[v]<de)tmp--;
}
ans+=tmp;
}
}
cout<<ans/2;
return 0;
} 总结：我在写这题时虽然没能想出正解，但看出了%60数据O(n^2)能过，于是用了个map来存重复数量，但是在循环内map每次新建，浪费了许多空间，需要先判断是否存在，这的确是我不知道的点，需要加强。 标签：赛道,tmp,王老师,三好学生,2024.8,de,100005,int,组月赛 From： https://www.cnblogs.com/qianqian2022/p/18391101