NC14524. 珂朵莉喊你一声大佬
描述
有n种大佬，第i种大佬有ai个
珂朵莉想让最少个数的一种大佬的个数最多
你可以创造m个任意种类的大佬，并且可以把一些大佬变成另一些大佬
x -> y意味着可以把任意个x类型的大佬变成y类型的大佬
一个大佬可以被转换多次
对于每个y，最多有一个x使得x -> y成立
输入描述
第一行两个数n,m
之后一行，第i个数xi表示第i种大佬可以被哪种大佬转换得到
如果xi为-1表示这种大佬不可以被任何大佬转换得到
之后一行，第i个数ai表示第i种大佬的个数
输出描述
输出一行一个数表示答案
答案即
你要求让最少个数的一种大佬的个数最多的方案
输出这个方案下最少个数的一种大佬的个数
示例1
输入:
5 5 -1 1 1 1 1 4 5 1 3 2
输出:
3
示例2
输入:
10 10 -1 1 1 2 1 5 5 6 10 5 6 1 7 1 7 1 10 5 1 1
输出:
4
C++14(g++5.4) 解法, 执行用时: 1494ms, 内存消耗: 37980K, 提交时间: 2020-06-11 08:54:29
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n,cnt;
ll m;
const int maxn=1e6+10;
ll c[maxn],d[maxn];
int a[maxn],deg[maxn],q[maxn],inn[maxn],vis[maxn];
bool topu(ll k)
{
int l=1,r=0;
ll p=m;
for(int i=0;i<=n;i++)
{
deg[i]=inn[i];
vis[i]=0;
d[i]=c[i];
}
for(int i=1;i<=n;i++)if(deg[i]==0)q[++r]=i;
while(l<=r)
{
int u=q[l++];
vis[u]=1;
if(d[u]<k)d[a[u]]-=k-d[u];
if(--deg[a[u]]==0)q[++r]=a[u];
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
ll sum=k-d[i];
vis[i]=1;
for(int j=a[i];j!=i;j=a[j])
{
sum+=k-d[j];
vis[j]=1;
}
p-=max(sum,(ll)0);
}
}
if(p+d[0]<0)return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==i)a[i]=-1;
if(a[i]!=-1)
{
inn[a[i]]++;
}
else a[i]=0;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
}
ll l=0,r=1e9,ans=0;
while(l<=r)
{
ll mid=(l+r)>>1;
if(topu(mid))ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1631ms, 内存消耗: 57456K, 提交时间: 2018-11-01 14:54:14
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,m,cnt,du[N],a[N],B[N],v[N],size[N],fa[N];
ll b[N],c[N];
queue<int>q;
inline int read(){
int x=0,f=0; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return f? n+1 : x;
}
inline void toposort(){
for(int i=1;i<=n;++i)
if(!du[i]) q.push(i);
while(!q.empty()){
int x=q.front(); q.pop();
v[++cnt]=x;
if(!(--du[fa[x]])) q.push(fa[x]);
}
for(int i=1;i<=n;++i)
if(du[i]){
int x=i;
while(1){
B[x]=i; du[x]=0;
x=fa[x]; if(x==i) break;
}
fa[i]=n+1;
v[++cnt]=i;
}
}
inline bool pd(ll x){
for(int i=1;i<=n;++i)
b[i]=c[i]-1ll*size[i]*x;
b[n+1]=m;
for(int i=1;i<=cnt;++i)
if(b[v[i]]<0) b[fa[v[i]]]+=b[v[i]];
return b[n+1]>=0;
}
int main(){
n=read(); m=read();
for(int i=1;i<=n;++i)
++du[fa[i]=read()],B[i]=i;
for(int i=1;i<=n;++i) a[i]=read();
toposort();
for(int i=1;i<=n;++i)
c[B[i]]+=a[i];
for(int i=1;i<=n;++i)
if(B[fa[i]]) fa[i]=B[fa[i]];//这个到底是干什么用的？
for(int i=1;i<=n;++i) ++size[B[i]];
ll l=0,r=2e9,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(pd(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}