随机化算法+贪心!

将3*k排序后分成3分,将第二第三份的和分别加起来,让和与500*k比较,都大于则输出,否则,随机生成2个数,在第二第三份中交换!

代码如下:

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
struct an
{
int w,lab;
}p[];
bool cmp(const an &a,const an &b)
{
return a.w<b.w;
}
int main()
{
int i,j,n,sa,sb,ans,a,b;
cin>>n;
for(i=;i<*n;i++){
cin>>p[i].w;
p[i].lab=i+;
}
sort(p,p+*n,cmp);
sa=;sb=;
for(i=n;i<n+n;i++)
sa+=p[i].w;
for(i=n+n;i<*n;i++)
sb+=p[i].w;
ans=n*;
bool flag=;
if(sa>ans&&sb>ans) flag=;
while(!flag){
a=rand()%n+n;
b=rand()%n+*n;
sa=sa-p[a].w+p[b].w;
sb=sb-p[b].w+p[a].w;
swap(p[a],p[b]);
if(sa>ans&&sb>ans){
flag=;
break;
}
}
for(i=;i<*n;i++)
cout<<p[i].lab<<endl;
return ;
}

最新文章

  1. nth-of-type在选择class的时候需要注意的一个小问题
  2. Linux iptables配置错误导致ORA-12535 &amp; ORA-12170
  3. SOA架构介绍和理解
  4. 转载:APP的上线和推广&mdash;&mdash;线上推广渠道
  5. [Effective JavaScript笔记]第3条:当心隐式的强制转换
  6. P1018 乘积最大
  7. 使用epel源安装依赖包时报错
  8. 【Linux】系统 之 Load
  9. Archlinux 安装配置指导 2015-05-24
  10. 任务调用及远端管理(基于Quartz.net)
  11. git上传本地文件到gitlab
  12. java反射机制--reflection
  13. ansible基础-roles
  14. C# 获取外网IP地址
  15. 除了binlog2sql工具外,使用python脚本闪回数据(数据库误操作)
  16. [转]SQL SERVER整理索引碎片测试
  17. 剑指offer:复杂链表的复制
  18. Hbuilder配置识别逍遥安卓模拟器
  19. zabbix_agentd客户端安装与配置(Linux操作系统)
  20. Game2048

热门文章

  1. 如何找出MySQL数据库中的低效SQL语句
  2. 在Tomcat中配置基于springside的项目
  3. 20141016--for 兔子
  4. 产品经理常用工具Axure、Visio、Mindmanager使用解析(摘)
  5. C/C++中浮点数格式学习——以IEEE75432位单精度为例
  6. 2016年11月ACM/ICPC亚洲区北京赛赛后总结
  7. Poj 2840 Big Clock
  8. JQ批量控制form禁用
  9. 在Linux上部署和操作Couchbase
  10. T-SQL实例 函数结果设置为列别名