牛牛数星星

[编程题]牛牛数星星

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

一闪一闪亮晶晶，满天都是小星星，牛牛晚上闲来无聊，便躺在床上数星星。

牛牛把星星图看成一个平面，左上角为原点(坐标为(1, 1))。现在有n颗星星，他给每颗星星都标上坐标(x_i，y_i)，表示这颗星星在第x行，第y列。

现在，牛牛想问你m个问题，给你两个点的坐标(a1, b1)(a2，b2)，表示一个矩形的左上角的点坐标和右下角的点坐标，请问在这个矩形内有多少颗星星（边界上的点也算是矩形内）。

输入描述:

第一行输入一个数字n(1≤n≤100000)，表示星星的颗数。
接下来的n行，每行输入两个数x_i和y_i(1≤x_i，y_i≤1000），表示星星的位置。
然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。
接下来m行，每行输入四个数字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）
题目保证两颗星星不会存在于同一个位置。

输出描述:

输出一共包含m行，每行表示与之对应的每个问题的答案。

示例1

输入

输出

算法知识视频讲解

Java

OFFER死哪去了

好像超时了。。。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[][] res = new int[1001][1001];
        while(sc.hasNext()){
            int n = sc.nextInt();
            for(int i=0;i<n;i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                res[a][b]=1;
            }
            int len = res.length;
            for(int i=1;i<len;i++){
                for(int j=1;j<len;j++){
                    res[i][j]=res[i][j]+res[i-1][j]+res[i][j-1]-res[i-1][j-1];
                }
            }
            int m = sc.nextInt();
            int count=0;
            for(int i=0;i<m;i++){
                int c = sc.nextInt();int d = sc.nextInt();int e = sc.nextInt();int f = sc.nextInt();
                count=res[e][f]-res[c-1][f]-res[e][d-1]+res[c-1][d-1];
                System.out.println(count);
            }
        }
        sc.close();
    }
}

发表于 2018-06-26 20:21:53 回复(2)