Java實作第九屆藍橋杯階乘位數

階乘位數

題目描述

小明維護着一個程式員論壇。現在他收集了一份"點贊"日志，日志共有N行。其中每一行的格式是：

ts id

表示在ts時刻編号id的文章收到一個"贊"。

現在小明想統計有哪些文章曾經是"熱帖"。如果一個文章曾在任意一個長度為D的時間段内收到不少于K個贊，小明就認為這個文章曾是"熱帖"。

具體來說，如果存在某個時刻T滿足該帖在[T, T+D)這段時間内(注意是左閉右開區間)收到不少于K個贊，該帖就曾是"熱帖"。

給定日志，請你幫助小明統計出所有曾是"熱帖"的文章編号。

【輸入格式】

第一行包含三個整數N、D和K。

以下N行每行一條日志，包含兩個整數ts和id。

對于50%的資料，1 <= K <= N <= 1000

對于100%的資料，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000

【輸出格式】

按從小到大的順序輸出熱帖id。每個id一行。

【輸入樣例】

7 10 2

0 1

0 10

10 10

10 1

9 1

100 3

100 3

【輸出樣例】

1

3

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。

不要使用package語句。不要使用jdk1.7及以上版本的特性。

主類的名字必須是：Main，否則按無效代碼處理。

import java.util.Arrays;
import java.util.Scanner;
class Main
{
    public static void main(String args[])
    {
        int n,d,k;  //輸入的N行每行一條日志，包含兩個整數ts 和id。   
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        d=sc.nextInt();
        k=sc.nextInt();
        ClickHot arr[]=new ClickHot[n];
        for(int i=0;i<n;i++)
            arr[i]=new ClickHot(sc.nextInt(),sc.nextInt()); //存放每組數字
        Arrays.sort(arr); //對其進行排序
        int parentId=arr[0].id; //先拿到第一個id
        int flag=0; //設定一個标志
        for(int i=0;i<n;i++)
        {
            if(i+k-1<n&&arr[i+k-1].id==parentId&&arr[i+k-1].ts-arr[i].ts<d&&flag==0) 
                // 後一個的id與（前一個id值相比較）：（這裡需要說明一下，這個id就是我所得到的變量parentId的值)
            {
                System.out.println(parentId); //輸出這個id 因為題目中隻要求輸出在同一個時間段有兩個贊即可
                flag=1;//這步設定變量，當後面來相同的，但是我不需要輸出了，因為兩個已經夠了
            }
            else if(arr[i].id!=parentId) //這步是如果我不相同id值，那麼我就把這個目前的id用我現在i數組中對應的id取代
            {
                parentId=arr[i].id; //把先前的id替換
                flag=0; //重新設定标志
                i=i-1; //因為我把上面一個設定了，此時我需要向上減一，然後再做比較，這樣相當于我開始時候i不做變換沒我把該取代的值取代掉
            }
        }
    }
}
class ClickHot implements Comparable<ClickHot>  //建立一個ClickHot類留存放兩個每次的兩個數字  一個是 ts 是td
{
    int ts,id;
    ClickHot(int a,int b)  //兩個變量
    {
        this.ts=a;
        this.id=b;
    }
 
    @Override
    public int compareTo(ClickHot o) {
        if(id==o.id)  //先對id做比較其次id相同對ts做比較
            return ts-o.ts;
        else
            return id-o.id;
    }
 
}