题解：P7168 [eJOI 2020] Triangulation (Day1)

Deepsick · 2026-11-05 09:53:47 · 题解

来个代码更短的题解。

首先，只有某条对角线横跨了 \frac{n}{2} 这个点（如果 n 是奇数，则是两个点），它才会产生不超过 \frac{n}{2} 的距离，因此如果这样的对角线存在，它一定是最优的。

称一条对角线编号较小的端点为左端点，较大的为右端点。由于对角线不交叉，因此在上述对角线中，一定存在一条，它的左端点最小同时右端点最大。记这条线为 (A,B)。

同时，注意到对角线将原图划分为的每个部分都是三角形。 ::::info[为什么？] 考虑每个部分的顶点数之和 S。每添加一条对角线，它的两个端点都在 S 中多出现一次，因此 S 会增加 2。所以最终 S=3n-6，而此时恰好有 n-2 个部分，所以这些部分都是三角形。 :::: 而 (A,B) 不可能和介于 1 到 A-1 之间的点构成三角形，否则与 A 的最小性矛盾；B+1 到 n-1 之间的点同理。因此，一定存在对角线（或边）(0,A) 和 (0,B)。

而对于 A<i<B，不可能存在对角线 (0,i)，因为它与 (A,B) 交叉。所以我们证明了：当 (A,B) 存在时，A 一定是使得 (0,i) 存在且 i\le \frac{n}{2} 的最大 i 值；B 同理。

而当找出的 A 和 B 相差不超过 1 时，就说明这样的 (A,B) 不存在，返回 (0,\lfloor\frac{n}{2}\rfloor) 即可。 ::::success[完整 AC 代码]

int query(int,int);
int solve(int n) {
    int i,j,m=n/2;
    for(i=m;i>1;i--) if(query(0,i)) break;
    for(j=n-m;j<n-1;j++) if(query(0,j)) break;
    if(j-i<=1) return i;
    else return i*n+j;
}

:::: AC 记录。