【ブルーブリッジカップ】ログ統計(java構造体ソート)
11870 ワード
タイトルの説明
明ちゃんはプログラマーフォーラムを守っています.今、彼は「いいね」のログを集めて、ログにはN行があります.各ローのフォーマットは次のとおりです.
ts id
ts時刻番号idを表す投稿に「賛」が受信された.
今、明ちゃんはどんな投稿が「ホット投稿」だったかを統計したいと思っています.もし1つの招待状がいずれかの長さDの時間帯にK個以上の賛を受け取ったことがあるならば、明ちゃんはこの招待状がかつて“ホット招待状”だったと思っています.
具体的には、ある時点でTがこのスレッドを満たして[T,T+D]この間(左閉右開区間であることに注意)K個以上の称賛を受けた場合、このスレッドは「ホットスレッド」だった.
与えられたログは、明ちゃんが「ホットスレッド」だったすべての投稿番号を統計するのを助けてください.
【入力フォーマット】第1行は、3つの整数N、D、Kを含む.以下のN行は、2つの整数tsおよびidを含む各行に1つのログを含む.
50%のデータに対して,1<=K<=N<=1000 100%のデータに対して,1<=K<=N<=100000 0<=ts<=100000 0<=id<=100000
【出力フォーマット】ホットスレッドidを小さい順に出力します.idごとに1行です.
【入力例】7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
【出力サンプル】1 3
リソース約定:ピークメモリ消費(仮想マシン含む)<256 M CPU消費<1000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.パッケージ文は使用しないでください.jdk 1は使用しないでください.7以降の機能.
メインクラスの名前は:Mainでなければなりません.そうしないと、無効なコードで処理されます.
問題を解く構想.
cとc++の思考によって言えば、idと時間を1つの構造体の中に置いて、それからidに従って並べ替えて、それから簡単な暴力ですが、javaの構造体はあまり書くことができません.これはjavaのカスタム並べ替えと構造体の並べ替えのブログです.
https://blog.csdn.net/xiao_you_you/article/details/104384005 https://blog.csdn.net/fyp19980304/article/details/80448060 https://www.cnblogs.com/shimu/p/10720066.html
コード#コード#
明ちゃんはプログラマーフォーラムを守っています.今、彼は「いいね」のログを集めて、ログにはN行があります.各ローのフォーマットは次のとおりです.
ts id
ts時刻番号idを表す投稿に「賛」が受信された.
今、明ちゃんはどんな投稿が「ホット投稿」だったかを統計したいと思っています.もし1つの招待状がいずれかの長さDの時間帯にK個以上の賛を受け取ったことがあるならば、明ちゃんはこの招待状がかつて“ホット招待状”だったと思っています.
具体的には、ある時点でTがこのスレッドを満たして[T,T+D]この間(左閉右開区間であることに注意)K個以上の称賛を受けた場合、このスレッドは「ホットスレッド」だった.
与えられたログは、明ちゃんが「ホットスレッド」だったすべての投稿番号を統計するのを助けてください.
【入力フォーマット】第1行は、3つの整数N、D、Kを含む.以下のN行は、2つの整数tsおよびidを含む各行に1つのログを含む.
50%のデータに対して,1<=K<=N<=1000 100%のデータに対して,1<=K<=N<=100000 0<=ts<=100000 0<=id<=100000
【出力フォーマット】ホットスレッドidを小さい順に出力します.idごとに1行です.
【入力例】7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
【出力サンプル】1 3
リソース約定:ピークメモリ消費(仮想マシン含む)<256 M CPU消費<1000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.パッケージ文は使用しないでください.jdk 1は使用しないでください.7以降の機能.
メインクラスの名前は:Mainでなければなりません.そうしないと、無効なコードで処理されます.
問題を解く構想.
cとc++の思考によって言えば、idと時間を1つの構造体の中に置いて、それからidに従って並べ替えて、それから簡単な暴力ですが、javaの構造体はあまり書くことができません.これはjavaのカスタム並べ替えと構造体の並べ替えのブログです.
https://blog.csdn.net/xiao_you_you/article/details/104384005 https://blog.csdn.net/fyp19980304/article/details/80448060 https://www.cnblogs.com/shimu/p/10720066.html
コード#コード#
package ;
import java.util.Arrays;
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int d=in.nextInt();
int k=in.nextInt();
ClickHot arr[]=new ClickHot[n];
for(int i=0;i<n;i++)
{
int time=in.nextInt();
int id=in.nextInt();
arr[i]=new ClickHot(time,id);//
}
Arrays.sort(arr);// id
int parentId=arr[0].id;// ID
boolean flag=false;//
for(int i=0;i<n;i++)
{
// id ,
// id k
// :
//
// d
if(i+k-1<n&&arr[i+k-1].id==parentId&&arr[i+k-1].ts-arr[i].ts<d&&!flag)
{
System.out.println(parentId);
flag=true;
}
else if(arr[i].id!=parentId)// id id, id
{
parentId=arr[i].id;
flag=false;//
i=i-1;//
}
}
}
}
class ClickHot implements Comparable<ClickHot>// id
{
int ts,id;
ClickHot(int ts,int id)//
{
this.ts=ts;
this.id=id;
}
public int compareTo(ClickHot o)// id ,
{
if(id==o.id)
return ts-o.ts;
else
return id-o.id;
}
}