暴力最高\(50\)吧，本地测试不太准跑得快的只得了\(10\)分，慢的却得了\(50\)分
暴力
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define bs bitset<70>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e6+5;
int n,a[N],m;
struct node
{
mutable int v;
bool operator < (const node& A)const
{
return v<A.v;
}
};
multiset<node> s;
int tmp[N];
int main()
{
speed();
freopen("sample1.in","r",stdin);
freopen("out.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s.insert({a[i]});
}
ll ans=0;
// cout<<"*******"<<endl;
while(s.size())
{
auto it=s.end();
int mi=1e9;
for(int j=1;j<=m;j++)
{
it--;
tmp[j]=(*it).v;
mi=min(tmp[j],mi);
if(it==s.begin())break;
}
s.erase(it,s.end());
for(int j=1;j<=m;j++,it--)
{
// cout<<tmp[j]<<" ";
tmp[j]-=mi;
if(tmp[j]>0)s.insert({tmp[j]});
}
// cout<<endl;
ans+=mi;
}
cout<<ans<<endl;
return 0;
}
其实这是一道性质题，发现了很显然，\(max(\frac{\sum a_i}{m},a[n])\)
点击查看代码
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define bs bitset<70>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e6+5;
ll n,a[N],m;
int main()
{
speed();
// freopen("sample1.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>m;ll sum=0,mx=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
sum+=a[i];
}
sort(a+1,a+1+n);
cout<<max((ll)ceil(1.0*sum/m),mx);
return 0;
}
T2 P9133 [THUPC 2023 初赛] 大富翁
我们可以把要求的转换为式子，设\(f(u,v)\)为\(u\)支配\(v\),题面有点歧义,不知道支配是算上过去和未来的，还是只算过去的
点击查看代码
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define bs bitset<70>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e6+5;
int n,a[N],m,w[N],f[N],dep[N],sz[N];
vector <int> edge[N];
struct ca
{
int w,id;
}q[N];
void dfs(int u)
{
dep[u]=dep[f[u]]+1;
sz[u]=1;
for(auto to:edge[u])
{
dfs(to);
sz[u]+=sz[to];
}
}
bool cmp(ca a,ca b){return a.w>b.w;}
int main()
{
speed();
freopen("sample2.in","r",stdin);
freopen("out.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=2;i<=n;i++)cin>>f[i],edge[f[i]].pb(i);
ll ans=0;
dfs(1);
for(int i=1;i<=n;i++)
{
q[i].id=i;q[i].w=sz[i]-dep[i]-w[i];
}
sort(q+1,q+1+n,cmp);
for(int i=1;i<=n;i++)
{
if(i&1)
ans+=q[i].w;
}
cout<<ans;
return 0;
}