結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー fmhrfmhr
提出日時 2015-05-29 09:45:20
言語 Go1.4
(1.4.2)
結果
AC  
実行時間 80 ms / 5,000 ms
コード長 2,145 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 33,400 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-25 00:21:27
合計ジャッジ時間 990 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

package main

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

////pq///////////////////////////////

type Item struct {
	//value    int
	priority int
	index    int
}

type PriorityQueue []*Item

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

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

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(item *Item, value int, priority int) {
	//item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

////nextInt////////////////////////////
var s = bufio.NewScanner(os.Stdin)

func next() string {
	s.Split(bufio.ScanWords)
	s.Scan()
	return s.Text()
}
func nextInt() int {
	i, e := strconv.Atoi(next())
	if e != nil {
		panic(e)
	}
	return int(i)
}

/////solve///////////////////////////////////////
func solve(l []int) {
	m := make(map[int]int)
	//fmt.Println(l)
	for _, v := range l {
		m[v] += 1
	}
	//fmt.Println(m)
	pq := make(PriorityQueue, len(m))
	i := 0
	for _, p := range m {
		pq[i] = &Item{
			//value:    v,
			priority: p,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)
	var ans int
	for pq.Len() >= 3 {
		a := make(map[int]int)
		ans += 1
		for i := 0; i < 3; i++ {
			item := heap.Pop(&pq).(*Item)
			a[i] = item.priority - 1
		}
		//fmt.Println(a)
		for _, p := range a {
			if p > 0 {
				item := &Item{
					//value:    v,
					priority: p,
				}
				heap.Push(&pq, item)
			}
		}
	}
	fmt.Println(ans)
}

func main() {
	//var T int
	//fmt.Scan(&T)
	T := nextInt()
	L := make([][]int, T)
	for i := 0; i < T; i++ {
		//var N int
		//fmt.Scan(&N)
		N := nextInt()
		L[i] = make([]int, N)
		for j := 0; j < N; j++ {
			L[i][j] = nextInt()
			//var s int
			//fmt.Scan(&s)
			//L[i][j] = s
		}
	}

	for i := 0; i < T; i++ {
		solve(L[i])
	}
}
0