途家秋招开发工程师笔试编程题 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;
}

#笔试题目##途家网##题解##笔经#