Background
In one of the countries of Caribbean basin all decisions were accepted by the simple majority of votes at the general meeting of citizens (fortunately, there were no lots of them). One of the local
parties, aspiring to come to power as lawfully as possible, got its way in putting into effect some reform of the election system. The main argument was that the population of the island recently had increased and it was to longer easy to hold general meetings.
The essence of the reform is as follows. From the moment of its coming into effect all the citizens were divided into K (may be not equal) groups. Votes on every question were to be held then in each
group, moreover, the group was said to vote “for” if more than half of the group had voted “for”, otherwise it was said to vote “against”. After the voting in each group a number of group that had voted “for” and “against” was calculated. The answer to the
question was positive if the number of groups that had voted “for” was greater than the half of the general number of groups.
At first the inhabitants of the island accepted this system with pleasure. But when the first delights dispersed, some negative properties became obvious. It appeared that supporters of the party, that
had introduced this system, could influence upon formation of groups of voters. Due to this they had an opportunity to put into effect some decisions without a majority of voters “for” it.
Let’s consider three groups of voters, containing 5, 5 and 7 persons, respectively. Then it is enough for the party to have only three supporters in each of the first two groups. So it would be able
to put into effect a decision with the help of only six votes “for” instead of nine, that would be necessary in the case of general votes.
Problem
You are to write a program, which would determine according to the given partition of the electors the minimal number of supporters of the party, sufficient for putting into effect of any decision,
with some distribution of those supporters among the groups.
Input
In the first line an only odd integerK— a quantity of groups — is written (1 ≤K≤ 101). In the second line there are writtenKodd integers, separated with a space. Those
numbers define a number of voters in each group. The population of the island does not exceeds 9999 persons.
Output
You should write a minimal quantity of supporters of the party, that can put into effect any decision.
Sample
有两个思路:
1 先排序,然后从最小的值中取半数+1的值,就得到解了
2 使用priority_queue,就可以不排序,直接大数出列,小数入列,也可以很容易解决。
两个思路的时间效率都是O(n),但是运行起来应该是第二个思路比较快点。
这里使用priority_queue来解题。
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
void DemocracyInDanger1025()
{
int k = 0, ans = 0, a = 0;
cin>>k;
priority_queue<int> pqu;
int i = 0;
for ( ; i <= (k>>1); i++)
{
cin>>a;
a = (a>>1) + 1;
pqu.push(a);
ans += a;
}
for ( ; i < k; i++)
{
cin>>a;
a = (a>>1) + 1;
if (a < pqu.top())
{
ans -= pqu.top() - a;
pqu.pop();
pqu.push(a);
}
}
cout<<ans;
}
int main()
{
DemocracyInDanger1025();
return 0;
}
分享到:
相关推荐
Democracy declined across Asia in 2021.md
Why Should the United States Should Spread Democracy.pdf
为流动民主辩护_In Defense of Fluid Democracy.pdf
贵族专制、民主政治和系统设计(ARISTOCRACY, DEMOCRACY, AND SYSTEM DESIGN)..................................................................................................................................
「信息安全」Enemies_at_the_gate_protecting_american_democracy_in_2020 - web安全 渗透测试 安全培训 安全意识 渗透测试 安全管理
克隆下来: git clone https://github.com/YOU/democracy.space.git 安装所需的节点模块: npm install 发展 source .template.env npm start 您的本地版本现在应该在 。 在Microsoft Windows上 阅读.template.env...
贵族专制、民主政治和系统设计(ARISTOCRACY, DEMOCRACY, AND SYSTEM DESIGN)..................................................................................................................................
Democracy and Common Interests
目录(Contents) 二十周年纪念版序言(PREFACE TO THE 20TH ANNIVERSARY EDITION) ...................... I 第一版序言(PREFACE TO...贵族专制、 民主政治和系统设计(ARISTOCRACY, DEMOCRACY, AND SYSTEM DESIGN)
digital-democracy.org 数字民主网站设置我们建议使用rbenv进行环境设置。 (注意:您也可以使用RVM,但不能同时安装两者!) 打开一个新的终端窗口。 git clone git@github....
programming there is a democracy of objects. Neither programming approach, of course, is the full story. Some problems—for instance, those that handle simple tasks such as adding up numbers in a file...
焦油坑(THE TAR PIT).............................................................................................................贵族专制、民主政治和系统设计(ARISTOCRACY, DEMOCRACY, AND SYSTEM DESIGN)
信息安全_数据安全_Your Democracy Needs You Taking APT 安全防护 信息安全 安全防御 业务风控
民主 Express&Angular应用程序,用于向参议院和众议院成员发送消息(c)2015年电子前沿基金会目录背景资料Democracy.io是用于联系参议院和众议院议员的应用程序。 它为各个成员联系表格提供了用户友好的包装。 它...
democracy’. Although one might expect to find low level of political trust in repressive authoritarian societies, survey data indicates that political trust in China is actually very high. Does this ...
1. Public education is the fundamental way to prepare children from diverse ethnic, religious, and class backgrounds to live as responsible citizens in a democracy. 2. The tuition of public in China ...
In the fall of 1998 Bill Joy and Mike Clary asked us to help establish a community of developers and companies around Sun's then-new Jini network technology. Jini is a simple distributed computing ...
「安全管理」信息安全_数据安全_Your Democracy Needs You Taking - 安全漏洞 安全体系 安全开发 WEB应用防火墙 漏洞预警 端点安全