2023/8/13大约 8 分钟
A:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
* @author:Skyme
* @create: 2023-08-13 13:37
* @Description:
*/
public class A {
static int n;
static int x[];
static int y[];
static int z[];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
// static public int search(int[] num){
// int l=0;
// int r=num.length-1;
// while (l<=r){
//
// }
// }
public static void main(String[] args) throws IOException {
//按样例来看,就是找出每个的中间值
//先排序后二分即可
n=Integer.parseInt(br.readLine());
x=new int[n];
y=new int[n];
z=new int[n];
for(int i=0;i<n;i++){
String[] s = br.readLine().split(" ");
x[i]=Integer.parseInt(s[0]);
y[i]=Integer.parseInt(s[1]);
z[i]=Integer.parseInt(s[2]);
}
Arrays.sort(x);
Arrays.sort(y);
Arrays.sort(z);
int mid=n/2;
long cnt = 0;
for(int i=0;i<n;i++){
cnt+=Math.abs(x[i]-x[mid]);
}
int index=0;
//要构造成队列
//那么第一个数就要加上mid在当前队列的位置与第一个位置的差值
//mid+1->第x个数
//
for(int i=0;i<n;i++){
cnt+=Math.abs(y[i]-y[mid])-Math.abs((mid+1)-(i+1));
}
for(int i=0;i<n;i++){
cnt+=Math.abs(z[i]-z[mid]);
}
if(n%2==0){
}else {
}
System.out.println(cnt);
//7 8 9 10 /4 2 0 2/ 6 3 0 3/ 8 12
//越靠近中心的那个数就减去中心差值
}
}C:
import java.io.BufferedReader;
import java.util.LinkedList;
import java.util.Scanner;
/**
* @author:Skyme
* @create: 2023-08-13 13:37
* @Description:
*/
public class C {
static class Node{
int idx;
int d;
public Node(int idx,int d){
this.idx=idx;
this.d=d;
}
}
static int n;
static int g[];
static int dist[];
static boolean st[];
static LinkedList<Node> linkedList=new LinkedList();
static int dx[]={-1,1};
static int m[];
static int cnt[]=new int[1000010];
static int ans=0;
public static void bfs(){
while (!linkedList.isEmpty()){
int size=linkedList.size();
while (size-->0){
Node node = linkedList.poll();
int idx=node.idx;
int t=node.d;//亮度
if(idx==n){
ans=t;
break;
}
if(m[idx]!=0){
if(!st[m[idx]]){
Node node1= new Node(m[idx],t+1);
st[m[idx]]=true;
linkedList.offer(node1);
}
}
for(int i=0;i<2;i++){
int nidx=idx+dx[i];
if(nidx>=1&&!st[nidx]){
st[nidx]=true;
Node node1=new Node(nidx,t+1);
linkedList.offer(node1);
}
}
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
g=new int[n+1];
dist=new int[n+1];
st=new boolean[n+1];
//构建一个传送数组
//表示当前点的下一个亮度相同的地方
m=new int[n+1];
//存放上一个相同的编号
st[1]=true;
linkedList.offer(new Node(1,0));
for(int i=1;i<=n;i++){
g[i]=sc.nextInt();
if(cnt[g[i]]!=0){
m[cnt[g[i]]]=i;//上一个的下一个是当前这个编号
}
cnt[g[i]]=i;//记录为上一个
}
bfs();
System.out.println(ans);
}
}D:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
/**
* @author:Skyme
* @create: 2023-08-13 14:44
* @Description:
*/
public class D {
static int p;
static int q;
static int n1;
static int n2;
static int n3;
static int k[];
static int max=Integer.MIN_VALUE;
static int min=Integer.MAX_VALUE;
//每一种的数量
public static void dfs(int x,int num,int legs){
if(x>=3||legs<0){
return;
}
if(x==2){
if(num*k[2]==legs) {
max=Math.max(num,max);
min=Math.min(num,min);
}
return;
}
// if(k[x]>legs){
// return;
// }
//第一种选择n个,那么剩下的就是p-n个
for(int i=0;i<=num;i++){
if(legs-i*k[x]>=0)
dfs(x+1,num-i,legs-i*k[x]);
}
}
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s = br.readLine().split(" ");
Scanner sc=new Scanner(System.in);
p=Integer.parseInt(s[0]);
q=Integer.parseInt(s[1]);
n1=Integer.parseInt(s[2]);
n2=Integer.parseInt(s[3]);
n3=Integer.parseInt(s[4]);
k=new int[3];
k[0]=n1;
k[1]=n2;
k[2]=n3;
dfs(0,p,q);
if(min==Integer.MAX_VALUE&&max==Integer.MIN_VALUE){
System.out.println(-1);
}else
System.out.println(min+" "+max);
}
}F:(WA）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
/**
* @author:Skyme
* @create: 2023-08-13 16:02
* @Description:
*/
public class F {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int n;//小猫的数量
static int p[];
static int v[];
static boolean st[];
static class Node{
int d;
int v;
public Node(int x,int y){
this.d=x;
this.v=y;
}
}
public static void main(String[] args) throws IOException {
//可以这样理解,有几种关系
//第一种就是位置小,但速度快
//第二种就是位置大,但速度慢
//那么这种情况一定会成为一组
//其余情况就不是一组
n=Integer.parseInt(br.readLine());
p=new int[n];
v=new int[n];
//维护一个数据结构->找到比自己速度大的或找到比自己
//物理里面是这样算的d1+v1*t=d2+v2*t->(v1-v2)*t=d2-d1->d2-d1/v1-v2>0?
int max=Integer.MIN_VALUE;
HashMap<Integer,Integer> map=new HashMap<>();
ArrayList<Node> list = new ArrayList<>();
for(int i=0;i<n;i++){
String[] s = br.readLine().split(" ");
p[i]=Integer.parseInt(s[0]);
max=Math.max(p[i],max);
v[i]=Integer.parseInt(s[1]);
Node node = new Node(p[i], v[i]);
if(!map.containsKey(p[i])){
map.put(p[i],v[i]);
list.add(node);
}
}
//将距离小于自己,但速度大于自己的合并为一类
//这一类只需要将速度最小且距离最大的放在最上面
//然后继续找即可
//先把相同起点的全部归位一类
//然后开始计算不同的
//构造一个Node节点,按速度排序,速度比自己大的都能追上自己然后合并为一类
//合并之后再按
//只要判断速度即可
}
}思路：
(难受)
看错题了，问的是：请问最终不再有追赶上的情况时，最多一组有多少只小猫？
思维题,根据题意可以知道，距离在前面且速度比这个大的一定能和这个合并(除非有起点相同的->速度小合并速度大的）无非就是这两种情况,所以如果起点一样,那么速度小的合并速度大的,如果起点不一样,那么距离前速度大的一定能与距离后速度小的合并为一组,所以先按距离排序,排出比自己距离小的,然后再按照速度排序,速度小的放最前面,最后我们每次找到最小的,算出与前面合并的即可,按距离找速度最小的,如果当前距离都小于上次合并的了,说明这个猫被合并过了我们直接忽略,特殊情况就是距离相同的(这个其实也考虑在排序里面了)如果距离相同,那么速度更大的则在前面,等合并的时候,肯定包括在里面(因为合并又是按速度排的,那么我取当前最小的时候,如果有相同最小,那肯定是速度大在前面等着被合并)，当速度相同的时候,那么肯定距离大的在后面,平行,而且距离大的只会合并前面比相同速度大的且距离比相同速度大的那些
关键计算集合
ans=Math.max(ans,cnt.get(node.idx)-s);
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
/**
* @author:Skyme
* @create: 2023-08-13 22:42
* @Description:
*/
public class F题复盘 {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static int n;//小猫的数量
static int p[];
static int v[];
static class Node{
int idx;
int d;
int v;
public Node(int idx,int x,int y){
this.idx=idx;
this.d=x;
this.v=y;
}
}
public static void main(String[] args) throws IOException {
ArrayList<Node> list = new ArrayList<>();
//思路就是先找到比自己距离小的,然后再找到比自己速度小的
//先排序,把比自己距离小的全部记录
//再排序,把速度比自己小的全部排出来
//合并->在自己之前的
n=Integer.parseInt(br.readLine());
p=new int[n+1];
v=new int[n+1];
for(int i=0;i<n;i++){
String[] s = br.readLine().split(" ");
p[i]=Integer.parseInt(s[0]);
v[i]=Integer.parseInt(s[1]);
Node node = new Node(i+1,p[i], v[i]);
list.add(node);
}
//先根据距离计算出在自己前面的
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if(o1.d== o2.d){//如果二者的起点位置相同,速度快的就在速度慢的前面
return o2.v-o1.v;
}
return o1.d-o2.d;
}
});
HashMap<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
Node node = list.get(i);//记录前面有多少个
cnt.put(node.idx,i+1);//记录自己前面多少个包括自己(方便后面合成一个集合)
}
Collections.sort(list, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if(o1.v== o2.v){//如果二者的起点位置相同,速度快的就在速度慢的前面
return o1.d-o2.d;
}
return o1.v-o2.v;
}
});
//每次找到最小的并合并前面的
int l=0;//上一次合并到的位置
int s=0;//上一次合并的个数
int ans=0;
for(int i=0;i<n;i++){
Node node = list.get(i);
if(node.d>l){
ans=Math.max(ans,cnt.get(node.idx)-s);
l=node.d;
s=cnt.get(node.idx);
}
}
System.out.println(ans);
}
}