http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3715

题意:有N个孩子投票选举leader,不能自己选自己。Sheldon想做leader,所以他就用糖果贿赂其他人,别的孩子就会将票投给他。问Sheldon最少要送多少糖果。

思路:枚举Sheldon做leader的票数(Sheldon原始的票数<= i < 100),将所有票数比他高的kid的得票一直减到票数比他少(按照给得票高的人投票的孩子所要的糖果数从小到大减),如果最后Sheldon的票数还是不够,就贿赂没投给他票且要的糖果数少的孩纸。最后输出花费的最少的糖果数。

 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF=<<;
int m[][];
int vis[],sum[]; struct node
{
int kid;
int candy;
friend bool operator <(node a,node b)
{
return a.candy < b.candy; //按糖果数排序
}
} c[];
int main()
{
int t,n,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(sum,,sizeof(sum));
memset(m,,sizeof(m));
for (int i = ; i <= n; i++)
{
scanf("%d",&x);
m[i][x] = ;//表示第i个孩子将票投给了x
sum[x]++;//记录每个人的得票数
}
for (int i = ; i <= n; i++)
{
scanf("%d",&x);
c[i-].kid = i; //将贿赂第i个孩子所需的糖果数保存在数组c中
c[i-].candy = x;
}
sort(c,c+n-);//按糖果数排序
int Min = INF;
for (int i = sum[]; i < n; i++)//枚举胜出的票数
{
if(i==) continue;
int get = sum[];//Sheldon的原始票数
int num = ; //记录所需的糖果数
memset(vis,,sizeof(vis));
for (int j = ; j <= n; j++)
{
int temp = sum[j];
if (temp >= i)//处理所有票数比他高的
{
for (int k = ; k < n-; k++)
{
if (m[c[k].kid][j])
{
vis[c[k].kid] = ;
num+=c[k].candy;
get++;
temp--;
if (temp < i)
break;
}
}
}
}
if (get <= i)
{
for (int k = ; k < n-; k++)
{
if (get==i)
break;
if (!vis[c[k].kid])
{
get++;
num+=c[k].candy;
}
}
if(num < Min) Min = num;
}
}
printf("%d\n",Min);
}
return ;
}

最新文章

  1. java中 IndexOf()、lastIndexOf()、substring()的用法
  2. 反编译apk时遇到的问题
  3. Android工作学习第5天之Activity的完全退出程序
  4. 设置ulimit值(Linux文件句柄数量)永久生效
  5. VBS基础篇 - 条件语句
  6. Python 学习笔记(三)Function
  7. label WordWrap
  8. CF_216_Div_2
  9. AutoMapper DynamicMap天坑
  10. 转: 关于异步promises
  11. hadoop1.2.1 MultipleOutputs将结果输出到多个文件或文件夹
  12. Thrift教程初级篇——thrift安装环境变量配置第一个实例
  13. 第4章 同步控制 Synchronization ----互斥器(Mutexes)
  14. windows使用Win32DiskImager安装树莓派系统
  15. PyPI可以使用的几个国内源
  16. python模块(os,sys,hashlib,collections)
  17. namenode No valid image files
  18. CentOS 7 输入中文 &amp; 安装搜狗输入法
  19. k8s的使用
  20. 【ARC065E】??

热门文章

  1. 洛谷——P2659 美丽的序列
  2. python环境配置以及基本知识
  3. 关于一个css布局的小记录
  4. [模拟赛FJOI Easy Round #2][T3 skill] (最小割+最大权闭合子图(文理分科模型))
  5. 关于 CMSIS 标准 及 STM32F10x的固件库
  6. 解决maven无法加载本地lib/下的jar包问题(程序包XXX不存在)
  7. 【00】angular学习网站
  8. ubuntu 16.04网卡找不到eth0
  9. vector实现
  10. Server Tomcat v8.0 Server at localhost failed to start.