自动搬运

查看原文

来自洛谷，原作者为

	phigy 互关，私信。 What is mind?No matter.What is matter?Never mind.

搬运于2025-08-24 22:27:16，当前版本为作者最后更新于2020-11-26 16:51:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然可以顺着枚举一遍。

预计得分10分。

#include "triangulation.h"
#include <iostream>

using namespace std;

int solve(int n)
{
    cin>>n;
    int i,j,k;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=i-1;j++)
        {
            if(query(j,n-i+j)==1)
            {
                return j*n+n-i+j;
            }
        }
    }
}

画图分析会发现：

一定有线段$AB$除非点$A$到$B$中有点与$0$有线段或$AB$距离为1。

显然$AB$上方的线段到$0$的距离一定大于$AB$到$0$的距离。

因此只需将$2$到$(n-1)$是否与$0$有线问一遍即可。

最后记得特判。

代码：

#include "triangulation.h"
#include <iostream>

using namespace std;

int d(int a,int b)
{
    if(a!=0)
    {
        return max(a,n-b);
    }
    else 
    {
        return max(b,n-b);
    }
}
int query(int a,int b)
{
    int x;
    cin>>x;
    return x;
}
int solve(int n)
{
    cin>>n;
    int i;
    int dis=9999999,ans=0;
    int l=1;
    for(i=2;i<=n-1;i++)
    {
        if(query(i,0)==1)
        {
            if(d(i,0)<dis)
            {
                dis=d(i,0);
                ans=i;
            }
            if(i-l>1&&d(l,i)<dis)
            {
                dis=d(l,i);
                ans=n*l+i;
            }
            l=i;
        }
    }
    int i=n-1;
    if(l+1!=i&&d(l,n-1)<ans)
    {
	dis=d(l,n-1);
	ans=n*l+n-1;
    }
    return ans;
}