利用TreeMap来解决P3029 [USACO11NOV] Cow Lineup S

P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

好了，我们首先要统计奶牛的种类数量n，好与接下来我们记录一个范围内的奶牛的数量作比较，一旦我们统计范围内的奶牛的数量m达到我们刚开始记录的奶牛的数量n我们就开始统计最小距离.

当然，首先我们要设计一个奶牛类，记录奶牛的编号和距离。

接下来统计奶牛的数量

在这里说一下题目的核心逻辑首先左边界从0开始，因为我们的第一头奶牛对应的是a【0】，那为什么右边界从-1开始呢，因为右边界随着枚举而增加。好比是从0开始到number-1，右边边界就从

0到number-1.核心逻辑是我们保证左边界所对应的编号的奶牛的数量始终为1，一旦大于一就进行递减，操作是舍弃最左边元素，就是说吧左边界往有移动一位，然后看看新的左边界是否对应的编号的奶牛的数量也是1，不是的话接着按上述操作进行。因为一旦在我们枚举的过程中，我们发现左边界的编号所对应的奶牛的数量不是1的话，那肯定在最右边又出现了以此左边界的编号，所以我们就将左边界右移一位，不影响我们的整体答案和种类数。当我们总类数目达到之前我们计算的时候，那就我们开始选取最小答案。

详情见代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {	public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");
number=Integer.parseInt(aStrings[0]);
int a;
int he=0;
for(a=0;a<number;a++) {String[] bStrings=br.readLine().split(" ");int b=Integer.parseInt(bStrings[0]);int c=Integer.parseInt(bStrings[1]);aaNainius[a]=new nainiu(b, c);if(tm1.containsKey(c)==false) {//统计有集中编号的奶牛，he变量就是奶牛的总数量tm1.put(c, 1);he++;}}
//System.out.println("DDD"+he);
Arrays.sort(aaNainius,0,number,new Comparator<nainiu>() {//将所有的额奶牛按照初始位置排序@Overridepublic int compare(nainiu o1, nainiu o2) {// TODO Auto-generated method stubreturn o1.juli-o2.juli;}
});
tm1.clear();//清空map集合的存储的内容
//System.out.println(hm1.size());
int left=0;//范围的左边界
int right=-1;//范围的右边边界
int sum=0;//种类的数量
int answer=Integer.MAX_VALUE;
//Arrays.fill(id, 0);
//System.out.println(Arrays.toString(aaNainius));
for(a=0;a<number;a++) {if(tm1.containsKey(aaNainius[a].id)==false) {//如果这一种编号不在我们的范围里那就种类数加一，把它放进我们的集合中tm1.put(aaNainius[a].id, 1);sum++;}else {int b1=tm1.get(aaNainius[a].id);b1++;//否则吧编号对应的数量加一tm1.put(aaNainius[a].id, b1);}right++;//右边随着边界扩展而不断扩展//qq1[++right]=new nainiu(aaNainius[a].juli, aaNainius[a].id);while (tm1.get(aaNainius[left].id)>1) {//当最左边的编号的数量大于一时，我们可以开始减减了int c1=tm1.get(aaNainius[left].id);c1--;tm1.put(aaNainius[left].id, c1);left++;//别忘记左边界加加}if(sum==he) {	answer=Math.min(answer, aaNainius[right].juli-aaNainius[left].juli //当凑其种类数目时开始选取最小值/*qq1[right].juli-qq1[left].juli*/);//System.out.println("AAA"+answer);if(right==5000) {System.out.println("CCC"+answer);}}
}
System.out.println(answer);//打印答案
}public static TreeMap<Integer, Integer> tm1=new TreeMap<>();//用于记录每种编号的奶牛的数目
//第一个变量是编号，第二个是编号对应的奶牛的数目public static nainiu[] aaNainius=new nainiu[50009];//奶牛类的数组//public static nainiu[] qq1=new nainiu[50009];public static int number;//奶牛的总数量}
class nainiu{//奶牛类：第一个变量记录每头奶牛的位置，接下来记录奶牛的idint juli;int id;public nainiu(int juli, int id) {super();this.juli = juli;this.id = id;}@Overridepublic String toString() {return "nainiu [juli=" + juli + ", id=" + id + "]";}}