【Codeforces 372A】Counting Kangaroos is Fun
2024-08-25 13:02:19
【链接】 我是链接,点我呀:)
【题意】
如果a[i]*2
【题解】
假设最后的方案是(ai,bi)
这里(ai,bi)表示下标为ai的袋鼠可以装进下标为bi的袋鼠里面
(这里袋鼠已经按照大小从小到大排序了)
则我们会发现,如果有(a1,b1),(a2,b2)...(ak,bk)这些方案的话(且这些方案合法)
我们总能让这个方案变成
a1~ak=1,2,3...k
b1~bk=n-k+1,n-k+2,n-k+3...n
因为对于每个(ai,bi)
ai只会减小,bi只会增大
那么下标为ai的袋鼠肯定还是小于下标为bi的袋鼠.
所以我们可以这么认为:
我们只会选择体型最小的x只袋鼠和体型最大的x只袋鼠进行配对装载
显然x另外一种错误的思路:
从大到小给每只袋鼠a[i]分配一个最大的且它能装得下的袋鼠a[j].
这种思路错误在于a[j]可能还可以给更小的袋鼠a[k]分配,
但是你把a[j]装下去了,可能除了a[j],a[i]之外没有其他袋鼠能装得下a[k]了。
比如例子:2 2 4 9
答案是2,但如果按照刚才说的错误思路的话,得到的答案会是3,因为9装了4之后,没有人能装2了
【代码】
import java.io.*;
import java.util.*;
public class Main {
static InputReader in;
static PrintWriter out;
public static void main(String[] args) throws IOException{
//InputStream ins = new FileInputStream("E:\\rush.txt");
InputStream ins = System.in;
in = new InputReader(ins);
out = new PrintWriter(System.out);
//code start from here
new Task().solve(in, out);
out.close();
}
static int N = (int)5e5;
static class Task{
int n;
int s[];
public void solve(InputReader in,PrintWriter out) {
s = new int[N+10];
n = in.nextInt();
for (int i = 1;i <= n;i++) {
s[i] = in.nextInt();
}
Arrays.sort(s, 1,n+1);
int x = 0;
int j = n;
for (int i = n/2;i >= 1;i--) {
if (s[i]*2<=s[j]){
x++;j--;
}
}
out.println(n-x*2 + x);
}
}
static class InputReader{
public BufferedReader br;
public StringTokenizer tokenizer;
public InputReader(InputStream ins) {
br = new BufferedReader(new InputStreamReader(ins));
tokenizer = null;
}
public String next(){
while (tokenizer==null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(br.readLine());
}catch(IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
最新文章
- BPM配置故事之案例4-子表
- Hoops随便记的
- Yii2的urlManager URL美化
- java-集合1
- Spring事务解析4-切面织入
- weblogic 12C 数据源配置出错的解决办法
- LeetCode(3) - Longest Substring Without Repeating Characters
- 告诉你一个真实的OpenStack:都谁在用,用来干什么?
- Wix - 教程
- kettle 连接Hadoop
- Ubuntu为已经安装的PHP7单独编译mysqli
- 进入html+css世界的正确姿势
- ivew实现table的编辑保存追加删除
- android开发学习——day6
- Shiro系列(3) - What is shiro?
- Linux Shell 基本语法
- spark脚本日志输出级别设置
- 两周撸一个掘金微信小程序
- MYSQL数据库里面的所有密码批量MD5加密
- 什么是mysql的事务和实现
热门文章
- 7章 Admin
- 深入浅出Android makefile(2)--LOCAL_PATH(转载)
- bzoj 1914: [Usaco2010 OPen]Triangle Counting 数三角形【叉积+极角排序+瞎搞】
- poj2096Collecting Bugs(概率期望dp)
- bzoj4987: Tree(树形dp)
- C#---数据库访问通用类、Access数据库操作类、mysql类 .
- 发生在升级OS X Yosemite后:修复各种开发环境
- C#模拟百度登录并到指定网站评论回帖(四)
- 利用freemarker导出页面格式复杂的excel
- 【Linux】Ubuntu下C语言访问MySQL数据库入门