途家 秋招 开发工程师 笔试 编程题 AC代码
两道数据都水，纯水过去的
因为数据太水了所以代码根本没有参考性！我的写法是有问题的！只是提供一个思路可以大家讨论一下
第一题：
纯贪心，t-i>4这个地方，写5是67%，写6及以上和3及以下是33%，写4就A了，无赖骗分
#include<cstdio>
using namespace std;
int main()
{
int m,s,t;
int dis,time;
scanf("%d%d%d",&m,&s,&t);
dis=0;
for (int i=1;i<=t;i++)
{
if (m>=10)
{
dis+=50;
m-=10;
}
else if (t-i>4)
{
m+=4;
}
else
{
dis+=13;
}
if (dis>=s)
{
printf("YES\n");
printf("%d\n",i);
break;
}
}
if (dis<s)
{
printf("NO\n");
printf("%d\n",dis);
}
return 0;
}
第二题： 正解不会，试着只对这R个特定点建图，求一波最小生成树，A了
最小生成树明显是错的，问了巨佬说这个题有问题，除了旅行商都有反例，可能是个错题
有空可以写下旅行商解法
#include<cstdio>
#include<algorithm>
using namespace std;
int f[10100];
struct numm
{
int x,y;
int v;
}qwq[10100];
bool cmp(numm a,numm b)
{
return (a.v<b.v);
}
int find(int x)
{
while (x!=f[x]) x=f[x];
return x;
}
int main()
{
int fx,fy,qxq;
int dis,ans;
int R[110];
int len;
int a,b,c;
int n,m,r;
scanf("%d%d%d",&n,&m,&r);
for (int i=1;i<=r;i++) scanf("%d",&R[i]);
sort(R+1, R+1+r);
len=0;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
bool isx,isy;
isx=isy=false;
for (int k=1;k<=r;k++)
{
if (R[k]==a) isx=true;
if (R[k]==b) isy=true;
if (isx==true && isy==true) break;
}
if (isx==false || isy==false) continue;
//printf("addpair: %d %d ==%d\n",a,b,c);
len++;
qwq[len].x=a;
qwq[len].y=b;
qwq[len].v=c;
}
qxq=0;
ans=0;
for (int i=1;i<=n;i++) f[i]=i;
sort(qwq+1,qwq+1+len,cmp);
for (int i=1;i<=len;i++)
{
fx=find(qwq[i].x);
fy=find(qwq[i].y);
if (fx!=fy)
{
f[fx]=fy;
qxq++;
//printf("addline= %d\n",qwq[i]);
ans+=qwq[i].v;
if (qxq==r-1) break;
}
}
printf("%d\n",ans);
return 0;
}
