[USACO19OPEN]I Would Walk 500 Miles 贪心

题目洛谷P5425(点击可跳转)

题目描述

Farmer John想要将他的编号为 $1 \ldots N$的 N N 头奶牛（ $N \leq 7500$ ）分为非空的 $K$ 组（ $2 \leq K \leq N $ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛$ x $ 和奶牛$y $ （其中$ 1 \leq x<y \leq N $ ）愿意为了见面走 $(2019201913x+2019201949y) \mod 2019201997$ 英里。

给定一个将 $ N$ 头奶牛分为$ K$ 个非空小组的分组方案，令 $M$ 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将 $N$ 头奶牛以最佳的方式分为 $K$组，使得$M $尽可能大。

输入输出格式

输入格式：

输入仅有一行，包含 $ N$ 和$ K $，用空格分隔。

输出格式：

输出最优的$M $。

输入输出样例

输入样例#1：

3 2

输出样例#1：

2019201769

说明

在这个例子中，奶牛$1$和奶牛$2$愿意为了见面走$2019201817$英里。奶牛$2$和奶牛$3$愿意走$2019201685$英里。奶牛$1$和奶牛$3$愿意走$2019201769$英里。所以，将奶牛$1$单独分为一组，奶牛$2$和奶牛$3$分为一组， $M=min(2019201817,2019201769)=2019201769 $ （这是我们在这个问题中能够达到的最佳结果）。

思路

我们可以把$x$奶牛与$y$奶牛”愿意为了见面行走的英里数”表示成一个函数:

\[g(x,y)=(2019201913 \times min(x,y)+2019201949 \times max(x,y))\mod 2019201997\]

同时我们定义
\[f(i)=min(g(i,j))\quad 1\leq j\leq n,i\ne j \]

那么显然答案是所有$f(i)$值由大到小排序的第$k-1$个,对应的情况是$f(i)$值由大到小排序的第$1$个动物到第$k-1$个动物每一个自成一组,剩下的所有动物成一组,共$k$组.

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define SIZE 7505
#define INF 0x7FFFFFFF
const long long P1=2019201913;
const long long P2=2019201949;
const long long Mod=2019201997;
inline int Fx(long long u,long long v){return (int)((P1*u+P2*v)%Mod);}
int n,k,x[SIZE];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)x[i]=INF;
    for(int u=1;u<=n;u++)
        for(int v=u+1;v<=n;v++)
        {
            int Tem=Fx(u,v);
            x[u]=min(x[u],Tem);
            x[v]=min(x[v],Tem);
        }
    sort(x+1,x+1+n);
    printf("%d\n",x[n-(k-2)]);
    return 0;
}