首页 > 试题广场 >

编程题1

[编程题]编程题1

热度指数：7444 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据,  1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

示例1

输入

输出

4 6
7 5
9 0

算法知识视频讲解

Java

牛客939797125号

java版本，用的堆排序，一开始输入用的scanner输出用println，通过70%，改完输入和输出后全部通过。输入的写法参考 Faster Input for Java (ku.ac.th)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int num=Reader.nextInt();
        PriorityQueue<int[]> points=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];
            }
        });
        for (int i = 0; i < num; i++) {
            int x=Reader.nextInt();
            int y=Reader.nextInt();
            points.offer(new int[]{x,y});
        }
        int[] p= points.poll();
        int x=p[0];
        int y=p[1];
        PrintWriter out=new PrintWriter(System.out);
        out.println(x+" "+y);
        while (!points.isEmpty()){
            p= points.poll();
            if (p[0]>x){
                x=p[0];
                out.println(p[0]+" "+p[1]);
            }
        }
        out.flush();
    }
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()){
                tokenizer=new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}

发表于 2022-07-17 00:47:43 回复(1)

Java

。201804111737858

用java写：：

通过率 70%，好难啊。到底怎么java才能100%,好像网上也没有java完全ac的大佬
import java.util.*;

/**
* @ClassName maxClass2Arraysort
* @Description TODO
* @Author Administrator
* @Data 20:57
* @Version 1.0
*/
public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int n= 0;
long [][]point = new long[N][2];
while(n<N){
point[n][0] = sc.nextInt();
point[n][1] = sc.nextInt();
n++;
}

sortArraylistLong(point);
// ArrayList<long[]> arrayList = new ArrayList<>();
// int [][] cons = new int[n][2];
long tmpMaxX = 0;
for(int t = 0;t < point.length; t++){
// System.out.println(pointX[t]+" "+pointY[t]);
if( t ==0 && point[t][1]>point[t+1][1] ){ //保证y最大

// arrayList.add(point[t]);
System.out.println(point[t][0]+" "+ point[t][1]);
tmpMaxX = point[t][0];
}else{
if(point[t][0] > tmpMaxX){
System.out.println(point[t][0]+" "+ point[t][1]);
tmpMaxX = point[t][0];
}
}

}

// for(int pps = arrayList.size()-1;pps >=0; pps--){
// System.out.printf("%s %s%n", arrayList.get(pps)[0], arrayList.get(pps)[1]);
// }

}

}

发表于 2020-03-19 23:08:07 回复(3)

Java

留一个offer给熊本熊吧

我的算法复杂度都是 nlog(n)了，还不行？MDZZ 求JAVA AC的代码

```java

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
public static void main(String[] args){
// test();
test_2();
}

public static void test(){
ArrayList<node> list = new ArrayList<>();
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
for(int i = 0; i < n; i++){
String[] test = br.readLine().split(" ");
int x = Integer.valueOf(test[0]);
int y = Integer.valueOf(test[1]);
list.add( new node(x,y) );
}
}catch (Exception e){
e.printStackTrace();
}

ArrayList<node> ans = find(list);
int i = ans.size();
for( ;i > 0; i--){
node temp = ans.get(i-1);
System.out.println(temp.toString());
}
}

public static class node{
public int x;
public int y;
public node(int x_pos, int y_pos){
x = x_pos;
y = y_pos;
}
@Override
public String toString() {
return x + " " + y;
}
}

static class mycmp implements Comparator<node>{
@Override
// 根据x轴和y轴的大小逆序排序
public int compare(node o1, node o2) {
return o1.x == o2.x ? o2.y - o1.y : o2.x - o1.x;
}
}

private static ArrayList<node> find(ArrayList<node> list){
ArrayList<node> ans = new ArrayList<>();
if(list.size() == 0){
return ans;
}
Collections.sort(list, new mycmp());
int y_max = -1;
Iterator<node> ito= list.iterator();
while (ito.hasNext()){
node temp = ito.next();
if(temp.y > y_max){
ans.add(temp);
y_max = temp.y;
}
}
return ans;
}

public static void test_2(){
ArrayList<node> ans = new ArrayList<>();
TreeMap<Integer, Integer> map = new TreeMap<>(new mmcpm());

try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
for(int i = 0; i < n; i++){
String[] test = br.readLine().split(" ");
int x = Integer.valueOf(test[0]);
int y = Integer.valueOf(test[1]);
if (!map.containsKey(x)){
map.put(x, y);
}else {
if(map.get(x) < y){
map.put(x, y);
}
}
}
}catch (Exception e){
e.printStackTrace();
}

int y_max = -1;
Set<Integer> keySet = map.keySet();
Iterator<Integer> iter = keySet.iterator();
while (iter.hasNext()) {
Integer x_pos = iter.next();
Integer y_pos = map.get(x_pos);
if(y_pos > y_max){
ans.add(new node(x_pos, y_pos));
y_max = y_pos;
}
}
for(int i = ans.size() - 1; i >= 0; i--){
System.out.println(ans.get(i).toString());
}
}

static class mmcpm implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
}

```

发表于 2019-08-04 17:17:11 回复(0)

Java

yxiaooo

import java.util.*;

class Point {
public int x,y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}

public int getX() {
return this.x;
}

public int getY() {
return this.y;
}

public void show() {
System.out.println(this.x+" "+this.y);
}
}

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Point[] x = new Point[n];
for (int i = 0; i < n; i++) {
Point p = new Point(sc.nextInt(),sc.nextInt());
x[i] = p;
}
Arrays.sort(x, new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2) {
return Integer.compare(p2.getX(),p1.getX());
}
});
List<Point> res = new LinkedList<>();
res.add(x[0]);
for (int i = 1; i < x.length; i++) {
if (x[i].getY() > ((LinkedList<Point>) res).getLast().getY()) {
res.add(x[i]);
}
}

for (Point p : res) {
p.show();
}
sc.close();
}
}

发表于 2019-03-16 06:14:47 回复(0)

Java

飞往自由

60%，求大佬看看哪地方需要改进

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class NO1 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner s = new Scanner(System.in);
        int num = s.nextInt();
        HashMap point = new HashMap();
        int[] point_x = new int[num];
        for(int i = 0; i<num; i++) {
            int x = s.nextInt();
            int y = s.nextInt();
            point.put(x, y);
            point_x[i] = x;
        }
        Arrays.sort(point_x);
        int key = -1;
        int[] result = new int[num];
        int index=0;
        for(int i=num-1; i>=0; i--) {
            if(point.get(point_x[i]) > key) {
                key = point.get(point_x[i]);
                result[index] = point_x[i];
                index++;
            }
        }
        for(int j=index-1; j>=0; j--) {
//            String fs = String.format("%d %d", result[j], point.get(result[j]));
            System.out.print(result[j]);
            System.out.print(" ");
            System.out.println(point.get(result[j]));
        }
    }

}

编辑于 2018-08-11 22:43:46 回复(0)

Java

天才小肥猫

70%超时。。求大佬们提意见～～啥意见都行

import java.util.*; 
public class Main { 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); int num = Integer.valueOf(scanner.nextLine());
        Point[] points = new Point[num];
        List maxPoints = new ArrayList();
        String[] line; for (int i = 0; i < num; i++) {
            line = scanner.nextLine().trim().split(" ");
            points[i] = new Point(Integer.valueOf(line[0]), Integer.valueOf(line[1]));
        }
        Arrays.sort(points);
        maxPoints.add(points[num - 1]); 
        int maxY = points[num - 1].y; for (int i = num - 2; i >= 0; i--) { if (points[i].y >= maxY) {
                maxPoints.add(points[i]);
                maxY = points[i].y;
            }
        }
        Collections.reverse(maxPoints);
        maxPoints.forEach(System.out::println);
    } 
    static class Point implements Comparator<Point> { 
        int x; 
        int y; 
        public Point(int x, int y) { 
            this.x = x; this.y = y;
        } 
        [@Override](/profile/992988)  
        public int compareTo(Point o) { 
            return Integer.compare(this.x, o.x);
        } 
        [@Override](/profile/992988)  
        public String toString() { 
            return x + " " + y;
        }
    }
}

编辑于 2018-04-03 17:51:02 回复(6)