专栏首页小樱的经验随笔POJ 2370 Democracy in danger(简单贪心)

POJ 2370 Democracy in danger(简单贪心)

Democracy in danger

Time Limit: 1000MS

Memory Limit: 65536K

Total Submissions: 3388

Accepted: 2508

Description

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. 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

The input of this problem contains two lines. In the first line an only natural number K <= 101 — a quantity of groups — is written. In the second line there are written K natural numbers, separated with a space. Those numbers define a number of voters in each group. In order to simplify the notion of "the majority of votes" we'll say that the number of groups also as the number of voters in each group is odd. You may also consider, that the population of the island does not exceeds 10001 persons.

Output

You should write an only natural number — a minimal quantity of supporters of the party, that can put into effect any decision.

Sample Input

3
5 7 5

Sample Output

6

Source

Ural State University Internal Contest October'2000 Junior Session

题目链接:http://poj.org/problem?id=2370

题解:以前挂的一些贪心的题没有做,有位大佬叫我写下题解,有些看不懂题意,我恭敬不如从命了,写点吧,算是复习下贪心吧!

题目大意是关于投票,已知k个组,这k个组中只要有一半以上通过了,就算通过了所以取k/2+1;要想去最少的通过人数,就想办法使得这k/2+1这些组的人数都是最少的,这时可以进行排序,然后取前k/2+1个组;每个组中只要有一半以上的人通过了,就算通过了,所以只要这些k/2+1组的每组超过一半的人通过了,就通过了;及a/2+1,a为每组的人数!

下面给出AC代码:

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 int main()
 7 {
 8     int a[110];
 9     int n;
10     while(scanf("%d",&n)!=EOF)
11     {
12         for(int i=0;i<n;i++)
13             scanf("%d",&a[i]);
14         sort(a,a+n);
15         int sum=0;
16         for(int i=0;i<n/2+1;i++)
17             sum+=a[i]/2+1;
18             printf("%d\n",sum);
19     }
20     return 0;
21 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #411 (Div. 2)(A,B,C,D 四水题)

    A. Fake NP time limit per test:1 second memory limit per test:256 megabytes inpu...

    Angel_Kitty
  • POJ 2209 The King(简单贪心)

    The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

    Angel_Kitty
  • UVA 11292 Dragon of Loowater(简单贪心)

    Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

    Angel_Kitty
  • 语音识别系统错误修正的开放挑战(CS CL)

    本文提出了提高语音自动识别系统性能的长期挑战。这项挑战的目标是研究如何在语音处理系统先前错误的基础上修正识别结果。描述了为该任务准备的数据集,并给出了评价标准。

    用户6853689
  • 基于统一的科学问题解释的重构(CS.AI)

    本文提出了一个框架,可以通过以解释为中心的语料库来重构对多项选择科学问题的解释。该框架以科学统一的概念为基础,通过结合两个不同的分数,对有关问题和候选答案的解释...

    蔡小雪7100294
  • 科学问题解释的统一重建(CS AI)

    本文提出了一个通过以解释为中心的语料库重构多项选择科学问题解释的框架。在科学统一概念的基础上,该框架利用两个不同分数的组合,对问题和候选答案的解释性事实进行排序...

    用户7095611
  • 问题难度对基于神经控制器学习的形态学发展影响的实验(cs AI)

    自然人在学习并适应从婴儿到成年时所面临的环境时,会经历其身体的形态发展过程。实际上,这是最重要的学习过程,即支持成人学习的过程。然而,在人工系统中,很少考虑形态...

    RockNPeng
  • md5算法原理一窥(其一)

        首先,需要了解的事,md5并不是传说中的加密算法,只是一种散列算法。其加密的算法并不是我们说所的那样固定不变,只是一种映射的关系。 所以解密MD5没有现...

    Gxjun
  • 语音表征的视觉引导自监督学习(Multimedia)

    自监督表示学习是近年来音频和视频模态的研究热点。然而,大多数研究工作通常只关注一种特定的模态或特征,而研究学习自我监督表征的两种模态之间的相互作用的工作非常有限...

    用户6869393
  • 语音表征的视觉引导自监督学习(Multimedia)

    自监督表示学习近年来引起了视、听两方面的广泛研究兴趣。然而,大多数研究工作通常只关注一种特定的模态或特征,而研究学习自我监督表征的两种模态之间的相互作用的工作非...

    李欣颖6837176

扫码关注云+社区

领取腾讯云代金券