牛客算法周周练13
A-最小生成树
链接：https://ac.nowcoder.com/acm/contest/6173/A
题目描述：
小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av
现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他
输入描述：
第一行一个正整数 n
第二行 n 个整数 a1,a2…an
输出描述：
输出边权和最小的生成树的边权之和
solution：
这题是贪心，只要将其余点与最小点相连，那么连上该点的边权最小。
#include<bits/stdc++.h>
using namespace std;
long long n,min1=0x3f3f3f3f,sum=0,a;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;
min1=min(a,min1);
sum+=a;
}
sum=sum+min1*(n-2);
cout<<sum;
}B-病毒感染
链接：https://ac.nowcoder.com/acm/contest/6173/B
题目描述：
有一天clccle和rqy走在某个国家的街头上,机智的rqy却发现周围的行人不太对劲,他们嘴里念念有词,说着"sqn tql!",一边漫无目的的行走,clccle也发现了这一点,却惊讶的发觉这种奇怪的病毒会向周围的城市,最终会感染整个国家,因为网络已经崩溃,所以她们忘记了自己所在的城市,她们唯一知道的是这种病毒是从当前她们所在的城市开始传播的,并且这个国家的所有城市到这个城市的距离和最小（所有道路的距离都为1）,现在给定聪明的你一张整个国家的地图,请你帮rqy和clccle找到她们现在可能在这个国家的哪一个城市.
输入描述：
两个整数n,m,代表这个国家一共有n个城市,城市之间只有m条道路
接下来m行,每行两个整数a,b代表城市a,b之间有一条联通的道路
输出描述：
多个整数,输出当前clccle和rqy可能所在的点
solution：
树形dp。找出每个点当作根的最远距离，然后找出最小值
#include<bits/stdc++.h>
using namespace std;
int h[200001],c=0,n,m;
int s[200001],f[200001],minn=0x7fffffff,b[200001];
struct Edge
{
int to,next;
}e[400001];
void Add(int x,int y)
{
e[++c].to=y;
e[c].next=h[x];
h[x]=c;
}
void dfs(int x,int prt)
{
int i,y;
s[x]=1;
for(i=h[x];i;i=e[i].next)
{
y=e[i].to;
if(y==prt)continue;
dfs(y,x);
s[x]+=s[y];
f[x]=max(f[x],s[y]);
}
f[x]=max(f[x],n-s[x]);
}
int main()
{
int i,x,y;
cin>>n>>m;
for(i=1;i<=n-1;i++)
{
cin>>x>>y;
Add(x,y);
Add(y,x);
}
dfs(1,0);
for(i=1;i<=n;i++)
if(f[i]<minn)
minn=f[i];
for(i=1;i<=n;i++)
if(f[i]==minn)
b[++b[0]]=i;
for(i=1;i<=b[0];i++)
cout<<b[i]<<" ";
}
C-Shopping
链接：https://ac.nowcoder.com/acm/contest/6173/C
题目描述：
你要买n件物品，其中有一些是凳子。
商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。
你有m辆购物车，请最小化你的花费。
输出描述：
第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数ai,bi，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ ai ≤ 1e5, 0 ≤ bi ≤ 1)。
输出描述：
每组数据输出一行一个实数表示最小花费，保留一位小数。
solution：
先找出有几条凳子c，然后求出n，m，c的最小值min1，这个最小值就是可以进行半价购买物品的数量，对物品进行排序，将花费最大的min1个物品进行半价购买，其余原价购买。
#include<bits/stdc++.h>
using namespace std;
int t,n,m,c,a[1005],b;
double s;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
s=0;
c=0;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b;
if(b==1)
c++;
}
sort(a,a+n);
m=min(n,min(m,c));
for(int i=n-1;i>=0;i--)
{
if(m)
{
s+=a[i]/2.0;
m--;
}
else
s+=a[i];
}
printf("%.1f\n",s);
}
}D-铺地毯
链接：https://ac.nowcoder.com/acm/contest/6173/D
题目描述：
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入描述：
第一行，一个整数n，表示总共有n张地毯。接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y轴方向的长度。第n+2行包含两个正整数x和y，表示所求的地面的点的坐标（x，y）。
输出描述：
输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
solution：
先将n张地毯的信息存下来，然后读取点，如果点在地毯里（x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]），更新该点的地毯编号
#include<bits/stdc++.h>
using namespace std;
int a[10005],b[10005],g[10005],k[10005],n,x,y;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i]>>g[i]>>k[i];
cin>>x>>y;
int c=-1;
for(int i=1;i<=n;i++)
{
if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i])
c=i;
}
cout<<c;
}E-金币馅饼
链接：https://ac.nowcoder.com/acm/contest/6173/E
题目描述：
最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。
奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，你必须走到下一列的某块馅饼旁边，并且，行数的变动不能超过1（也就是说，如果现在你站在坐标为(r,c)的馅饼边上，下一步你可以走到坐标为(r-1,c+1),(r,c+1),或者(r+1,c+1)的馅饼旁边）。当你从一块馅饼边经过，你就可以拿走馅饼里所有的金币。当然啦，你一定不会愿意因半路离开草地而失去唾手可得的金币，但，最终你一定得停在坐标为(R,C)的馅饼旁边。
现在，你拿到了一张标记着馅饼矩阵中，每一块馅饼含金币数量的表格。那么，按照规则，你最多可以拿到多少金币呢？
输入描述：
第1行: 两个用空格隔开的整数，R和C第2..R+1行: 每行包含C个用空格隔开的正整数，依次表示一行中从左往右各个馅饼里金币的数量
输出描述：
第1行: 输出一个正整数，表示你所能收集到的最大金币数目
solution：
这题是dp，从（1，1）点开始存储，每次dp范围往下一行（直到超出范围），对下一列的金币进行dp求解，输出（R，C）的金币数量
#include<bits/stdc++.h>
using namespace std;
int dp[505][505],n,m,a[505][505];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
memset(dp,0,sizeof(dp));
dp[0][0]=a[0][0];
for(int i=1;i<m;i++)
{
int c=min(i+1,n);
for(int j=0;j<c;j++)
{
if(j==0)
dp[j][i]=max(dp[j][i-1],dp[j+1][i-1])+a[j][i];
else if(j==n-1)
dp[j][i]=max(dp[j][i-1],dp[j-1][i-1])+a[j][i];
else
dp[j][i]=max(max(dp[j][i-1],dp[j-1][i-1]),dp[j+1][i-1])+a[j][i];
}
}
cout<<dp[n-1][m-1];
}
投递虾皮信息等公司10个岗位 >
