博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Round 428 B Game of the rows 贪心 思维
阅读量:7076 次
发布时间:2019-06-28

本文共 1946 字,大约阅读时间需要 6 分钟。

  题目链接: http://codeforces.com/contest/839/problem/B

  题目描述: 有K种人, 有N排的11, 1111, 11的座位, 要求不同种人不能坐在相邻的位置, 给你K种人每种人的人数, 问能不能安排的下?

  解题思路: 首先我们先放不小于三个的,挨个遍历, 只能放4 或者 2 * 2, 先放4, 再放 2 * 2 如果这时候不够放了, 直接输出NO

    然后就剩下一个的还有两个的, 我们先放两个的, 两个当然放在2是最优的, 然后再放4, 这时注意放4之后1的数量加加, 这样的话如果四个或者两个都没有的话可以拆成两个1

    最后就只有一堆一个了, 我们先看1还有没有, 有就放1 ,没有放2, 再则放4, 同时1加加, 这样最后判一遍放没放完就行了

  代码: 

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define meminf(a) memset(a,0x3f,sizeof(a))using namespace std;int a[107];int main() { int n, k; cin >> n >> k; for( int i = 1; i <= k; i++ ) { cin >> a[i]; } int s4 = n; int s2 = n << 1; int s1 =0; for( int i = 1; i <= k; i++ ) { while( s4 > 0 && a[i] >= 3 ) { s4--; a[i] -= 4; } if( s4 == 0 ) break; } for( int i = 1; i <= k; i++ ) { while( s2 > 0 && a[i] >= 3 ) { s2 -= 2; a[i] -= 4; } } if( s2 < 0 ) { cout << "NO" << endl; return 0; }// for( int i = 1; i <= k; i++ ) {// cout << a[i] << " ";// }// cout << endl; for( int i = 1; i <= k; i++ ) { if( a[i] == 2 ) { if( s2 > 0 ) { s2--; a[i] -= 2; } else if( s4 > 0 ) { s4--; a[i] -= 2; s1++; } else if( s1 >= 1 ) { s1 -= 2; a[i] -= 2; } } } if( s1 < 0 ) { cout << "NO" << endl; return 0; } for( int i = 1; i <= k; i++ ) { if( a[i] >= 2 ) { cout << "NO" << endl; return 0; } } for( int i = 1; i <= k; i++ ) { if( a[i] == 1 ) { if( s2 > 0 ) { s2--; a[i] = 0; } else if( s4 > 0 ) { s4--; s1++; a[i] = 0; } else if( s1 > 0 ) { s1--; a[i] = 0; } } } for( int i = 1; i <= k; i++ ) { if( a[i] > 0 ) { cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0;}
View Code

  思考: 代码写的巨丑, 昨天做的CF, 卡在B题一直出不来, 自己刚开始贪心4是对的, 但是后来应该有好多情况没有, 我多考虑造成结果错了, 还是没想清楚

 

转载于:https://www.cnblogs.com/FriskyPuppy/p/7356657.html

你可能感兴趣的文章
Codeforces Round #428 A. Arya and Bran【模拟】
查看>>
【设计模式】抽象工厂模式
查看>>
OO第四次博客
查看>>
面试STAR法则
查看>>
spark 操作hbase
查看>>
[LeetCode]Balanced Binary Tree
查看>>
Sqlitekit 封装管理
查看>>
8、log4e
查看>>
volatile 可见性的模拟分析示例
查看>>
2016.04.22-2016.04.28这周工作时间和内容
查看>>
jSignature签字板保存为图片
查看>>
node.js学习笔记--day1
查看>>
Delphi中Move、CopyMemory操作
查看>>
九、sparkStream的scala示例
查看>>
七、并发容器ConcurrentHashMap
查看>>
CentOS 6.4 yum快速搭建Zabbix 2.2版本(中文)
查看>>
MySQL密码丢失,解决方法
查看>>
20135306黄韧[2.72 2.77 3.70](http://i.cnblogs.com/EditPosts.aspx?opt=1)
查看>>
配置Redis客户端
查看>>
easyui datagrid 相关取数据总结
查看>>