分类：贪心

【优先队列/贪心】The Average

In a speech contest, when a contestant finishes his speech, the judges will then grade his performance. The staff remove the highest grade and the lowest grade and compute the average of the rest as the contestant’s final grade. This is an easy problem because usually there are only several judges.

Let’s consider a generalized form of the problem above. Given n positive integers, remove the greatest n1 ones and the least n2 ones, and compute the average of the rest.

继续阅读【优先队列/贪心】The Average

【贪心】小A与204

链接：https://ac.nowcoder.com/acm/contest/317/B
来源：牛客网

小a非常喜欢204这个数字，因为′a′+′k′=204。
现在他有一个长度为nn的序列，其中只含有2,0,4这三种数字
设aiai为序列中第ii个数，你需要重新排列这个数列，使得∑ni=1(ai−ai−1)2最大(公式的含义是：每个数与前一个数差的平方的和)
注意：我们默认a0=0

继续阅读【贪心】小A与204

牛客练习赛29-A 可持久化动态图上树状数组维护01背包

可持久化动态图上树状数组维护01背包
请允许我吐槽一下这个劝退人的题目，实际题与题目无关。
题目：

你有一个长度为 n 序列 {a}(序列下标从1开始) ，每次可以从任意位置 i 花费 ai*i 的代价来把 ai 删除。
注意，删除后 ai 后面的数会依次向前补上（下标 -1 ) 。

求把整个序列删完的最小代价。

继续阅读牛客练习赛29-A 可持久化动态图上树状数组维护01背包

Codeforces-1029A Many Equal Substrings

You are given a string t consisting of n lowercase Latin letters and an integer number k.Let’s define a substring of some string  with indices from  to r as .
Your task is to construct such string s of minimum possible length that there are exactly k positions i such that . In other words, your task is to construct such string s of minimum possible length that there are exactly k substrings of s equal to .It is guaranteed that the answer is always unique.

继续阅读Codeforces-1029A Many Equal Substrings

Codeforces-1000B B Light It Up

Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment 0 and turn power off at moment M. Moreover, the lamp allows you to set a program of switching its state (states are “lights on” and “lights off”). Unfortunately, some program is already installed into the lamp.

继续阅读Codeforces-1000B B Light It Up