[USACO19OPEN]I Would Walk 500 Miles 贪心

淡淡的烟草味﹌ 2021-10-19 04:52 243阅读 0赞

# 题目 [洛谷P5425(点击可跳转)][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;
    }

转载于:https://www.cnblogs.com/TaylorSwift13/p/11169057.html

[P5425]: https://www.luogu.org/problemnew/show/P5425