結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー tnoda_tnoda_
提出日時 2015-01-22 01:08:16
言語 Go1.4
(1.4.2)
結果
AC  
実行時間 78 ms / 5,000 ms
コード長 1,663 bytes
コンパイル時間 3,706 ms
コンパイル使用メモリ 35,140 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-25 00:10:05
合計ジャッジ時間 4,537 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
6,816 KB
testcase_01 AC 78 ms
6,820 KB
testcase_02 AC 41 ms
6,820 KB
testcase_03 AC 78 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type item struct {
	len int // value
	n   int // weight
}

type priorityQueue []*item

func (pq priorityQueue) Len() int { return len(pq) }

func (pq priorityQueue) Less(i, j int) bool {
	return pq[i].n > pq[j].n
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *priorityQueue) Push(x interface{}) {
	item := x.(*item)
	*pq = append(*pq, item)
}

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Split(bufio.ScanWords)
	if !sc.Scan() {
		panic("could not scan a word from the reader")
	}
	return sc.Text()
}

func nextInt() int {
	i, e := strconv.Atoi(next())
	if e != nil {
		panic(e)
	}
	return i
}

func nextLong() int64 {
	i, e := strconv.ParseInt(next(), 10, 64)
	if e != nil {
		panic(e)
	}
	return i
}

func nextLine() string {
	sc.Split(bufio.ScanLines)
	if !sc.Scan() {
		panic("could not scan a line from the reader")
	}
	return sc.Text()
}

func solve() {
	n := nextInt()
	a := make(map[int]int)
	for i := 0; i < n; i++ {
		x := nextInt()
		a[x]++
	}
	pq := make(priorityQueue, 0, n)
	for i, v := range a {
		item := &item{
			len: i,
			n:   v,
		}
		pq = append(pq, item)
	}
	heap.Init(&pq)
	z := 0
	for pq.Len() >= 3 {
		x := make([]*item, 3)
		for i := 0; i < 3; i++ {
			x[i] = heap.Pop(&pq).(*item)
			x[i].n--
		}
		for i := 0; i < 3; i++ {
			if x[i].n > 0 {
				heap.Push(&pq, x[i])
			}
		}
		z++
	}
	fmt.Println(z)
}

func main() {
	t := nextInt()
	for i := 0; i < t; i++ {
		solve()
	}
}
0