简单个人网站,网页设计色彩搭配,百度关键字排名软件,阿里巴巴电子商务网站P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
好了#xff0c;我们首先要统计奶牛的种类数量n#xff0c;好与接下来我们记录一个范围内的奶牛的数量作比较#xff0c;一旦我们统计范围内的奶牛的数量m达到我们刚开始记录的奶牛的数量n我…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 scnew Scanner(System.in);
BufferedReader brnew BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1new PrintWriter(System.out);
String[] aStringsbr.readLine().split( );
numberInteger.parseInt(aStrings[0]);
int a;
int he0;
for(a0;anumber;a) {String[] bStringsbr.readLine().split( );int bInteger.parseInt(bStrings[0]);int cInteger.parseInt(bStrings[1]);aaNainius[a]new nainiu(b, c);if(tm1.containsKey(c)false) {//统计有集中编号的奶牛he变量就是奶牛的总数量tm1.put(c, 1);he;}}
//System.out.println(DDDhe);
Arrays.sort(aaNainius,0,number,new Comparatornainiu() {//将所有的额奶牛按照初始位置排序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 left0;//范围的左边界
int right-1;//范围的右边边界
int sum0;//种类的数量
int answerInteger.MAX_VALUE;
//Arrays.fill(id, 0);
//System.out.println(Arrays.toString(aaNainius));
for(a0;anumber;a) {if(tm1.containsKey(aaNainius[a].id)false) {//如果这一种编号不在我们的范围里那就种类数加一把它放进我们的集合中tm1.put(aaNainius[a].id, 1);sum;}else {int b1tm1.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 c1tm1.get(aaNainius[left].id);c1--;tm1.put(aaNainius[left].id, c1);left;//别忘记左边界加加}if(sumhe) { answerMath.min(answer, aaNainius[right].juli-aaNainius[left].juli //当凑其种类数目时开始选取最小值/*qq1[right].juli-qq1[left].juli*/);//System.out.println(AAAanswer);if(right5000) {System.out.println(CCCanswer);}}
}
System.out.println(answer);//打印答案
}public static TreeMapInteger, Integer tm1new TreeMap();//用于记录每种编号的奶牛的数目
//第一个变量是编号第二个是编号对应的奶牛的数目public static nainiu[] aaNainiusnew nainiu[50009];//奶牛类的数组//public static nainiu[] qq1new 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 ];}}
