結果

問題 No.120 傾向と対策：門松列（その１）
ユーザー fmhrfmhr
提出日時 2015-05-28 01:21:01
言語 Go
(1.22.1)
結果
AC  
実行時間 1,076 ms / 5,000 ms
コード長 2,101 bytes
コンパイル時間 12,855 ms
コンパイル使用メモリ 228,744 KB
実行使用メモリ 8,560 KB
最終ジャッジ日時 2024-10-10 18:49:49
合計ジャッジ時間 16,899 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,071 ms
8,364 KB
testcase_01 AC 1,068 ms
8,488 KB
testcase_02 AC 532 ms
8,560 KB
testcase_03 AC 1,076 ms
8,492 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 v, 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[item.value] = item.priority - 1
		}
		//fmt.Println(a)
		for v, 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)
	L := make([][]int, T)
	for i := 0; i < T; i++ {
		var N int
		fmt.Scan(&N)
		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