努力把平凡的日子堆砌成伟大的人生
第一题 简单贪心
题目意思:你有n个u盘,以及内存为m的文件,可以分开装到不同的u盘里面最少需要几个
解题思路:我们要使用的最少,那我肯定优先使用最大的就是最优的
时间复杂度:o(nlogn) 排序
int t,n,m;
void solve()
{
cin>>n>>m;
vector<int> a(n);
for(auto&v:a) cin>>v;
sort(a.begin(),a.end(),greater<int>());
int sum=0,cnt=0;
for(auto&v:a){
sum+=v;
cnt++;
if(sum>=m) break;
}
cout<<cnt<<endl;
return ;
}
第二题 简单组合数
题目意思:给定你n本书,一共有m种类型,可以选择两本书,如果的书是不同类型的算一次贡献,求总贡献
解题思路:明显的类似排列组合第一种树可以和后面所有的书组合,后面的就不能和前面的组合
时间复杂度:o(nlogn) mp
void solve()
{
cin>>n>>m;
map<int,int> mp;
vector<int> a(n);
for(auto&v:a){
cin>>v;
mp[v]++;
}
int sum=n,ans=0;
for(auto&v:a){
mp[v]--;
sum--;
ans+=sum-mp[v];// 除了自己之外和后面所有和自己类别不一样的书进行组合
}
cout<<ans<<endl;
return ;
}
第三题 +1-1的典型操作
题目意思:给定一个序列,每一次操作可以使得任意一个位置+1,其他一个位置-1
求使得最大值-最小值最小的最少操作次数
解题思路:典型的+1 -1 具有一个很明显的特点就是总和是永远不变的,那么我们要使得
最大值和最小值的差值最小明显的就是让所有数趋近于平均值即可,也就是最大值-最小值
<=1,那我们如何使得操作次数最少呢?最后每一个数要么是平均值,要么是平均值+1,明显的
思路是优先最大的变成平均值+1即可
时间复杂度:o(nlogn) 排序
void solve()
{
cin>>n;
int sum=0;
vector<int> a(n);
for(auto&v:a) cin>>v,sum+=v;
int m=sum/n,pos=sum%n;
int ans=0;
sort(a.begin(),a.end(),greater<int>());
for(int i=0;i<n;i++){
if(i<pos) ans+=abs(a[i]-m-1);
else ans+=abs(a[i]-m);
}
cout<<ans/2<<endl;
return ;
}
第四题 最优策略的选择
题目意思:你要买k个工具,具有s元钱,给定n天兑换美元和英镑的汇率,以及m个物品
需要使用的货币购买以及费用,求解最早可以说明时候购买,并且买的每一个商品的编号以及购买时间
解题思路:首先我们现需要发现题目的性质,1.晚买的话一定不会比早买差,因为我可以使用之前的汇率去兑换就好了,所以我们发现具有前2.缀性,也就是汇率可以用有前缀最小值,同时我们维护一个下标,表示当前最优是那一天,接着我们利用1,可以发现具有了二分的性质,
所以我们可以使用二分来进行筛选时间,接着每一次都按照最优的来给每一个商品的价格来排序,选择前k个即可
时间复杂度:o(nlognlogn) 二分+内置排序 对于1e5范围这个时间复杂度是ok的
void solve()
{
cin>>n>>m>>k>>s;
vector<int> a(n+1),b(n+1),ida(n+1),idb(n+1);
vector<PII> op(m+1),ans(k);
a[0]=b[0]=2e9;
for(int i=1;i<=n;i++){
int x; cin>>x;
if(x<a[i-1]){
a[i]=x;
ida[i]=i;
}
else{
a[i]=a[i-1];
ida[i]=ida[i-1];
}
}
for(int i=1;i<=n;i++){
int x; cin>>x;
if(x<b[i-1]){
b[i]=x;
idb[i]=i;
}
else{
b[i]=b[i-1];
idb[i]=idb[i-1];
}
}
for(int i=0;i<m;i++){
int x,y; cin>>x>>y;
op[i]={x,y};
}
//找到前缀的最小值
auto check = [&](int mid){
int x=a[mid],idx=ida[mid];
int y=b[mid],idy=idb[mid];
vector<PII> res(m);
vector<int> cnt(m);
for(int i=0;i<m;i++){
auto [t,p]=op[i];
if(t==1) res[i]={p*x,i};//记录此时需要多少元
else res[i]={p*y,i};
}
sort(res.begin(),res.end());// 从小到大排序即可
int need=0;
for(int i=0;i<k;i++){
auto [p,d]=res[i];
need+=p;
ans[i]={res[i].second+1,op[res[i].second].first == 1 ? idx : idy};
}// 同时存下购买时间
return need <= s ;
};
int l=1,r=n;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
// 当二分的值可能是不存在的时候我们可以利用此时的l来再次check一次即可
if(!check(l)) cout<<-1<<endl;
else{
cout<<l<<endl;
for(int i=0;i<k;i++){
auto [x,d]=ans[i];
cout<<x<<' '<<d<<endl;
}
}
return ;
}
第五题 lca的直接考察
题目意思:给定n个点,m条边,求带上每一条边之后的生成树的值最小
解题思路:构造最小生成树,然后维护边和边的最大值,lca求解即可
struct code{
int a,b,w,id;
bool operator<(const code&t){
return w<t.w;
}
};
vector<PII> g[N];
void solve()
{
cin>>n>>m;
vector<code> edge(m+1);
vector<int> p(n+1),depth(n+1,0x3f3f3f3f);
vector<array<int,21>> fa(n+1);
vector<array<int,21>> fv(n+1);
int sum=0;
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++){
int a,b,w; cin>>a>>b>>w;
edge[i]={a,b,w,i};
}
sort(edge.begin()+1,edge.end());
auto add = [&](int a,int b,int w){
g[a].push_back({b,w});
};
function<int(int)> find = [&](int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
};
auto kuskra = [&](){
for(int i=1;i<=m;i++){
auto [a,b,w,_]=edge[i];
int fa=find(a),fb=find(b);
if(fa!=fb){
add(fa,fb,w);
add(fb,fa,w);
sum+=w;
p[fa]=fb;
}
}
};
kuskra();
auto bfs = [&](){
queue<int> q;
depth[0]=0,depth[1]=1;
q.push(1);
while(!q.empty()){
auto t=q.front(); q.pop();
for(auto&[v,w]:g[t]){
if(depth[v]>depth[t]+1){
depth[v]=depth[t]+1;
q.push(v);
fa[v][0]=t;
fv[v][0]=max(fv[v][0],w);
for(int k=1;k<=20;k++){
fv[v][k]=max(fv[v][k-1],fv[fa[v][k-1]][k-1]);
fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
};
bfs();
auto lca = [&](int a,int b){
int ans=0;
if(depth[a]<depth[b]) swap(a,b);
for(int k=20;k>=0;k--)
if(depth[fa[a][k]]>=depth[b]){
ans=max(ans,fv[a][k]);
a=fa[a][k];
}
if(a==b) return ans;
for(int k=20;k>=0;k--)
if(fa[a][k]!=fa[b][k]){
ans=max(ans,fv[a][k]);
ans=max(ans,fv[b][k]);
a=fa[a][k];
b=fa[b][k];
}
return max({ans,fv[a][0],fv[b][0]});
};
vector<int> ans(m+1);
for(int i=1;i<=m;i++){
auto [a,b,w,id]=edge[i];
ans[id]=sum+w-lca(a,b);
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return ;
}
6