传送门:AtCoder
题目描述:
There is a row of L chairs. Now, N groups of people will come and take seats in order. Each group
consists of one or two people, and the i-th group to come consists of ai people. The total number of people equals L.
Each group will randomly choose unoccupied chairs where all group members can sit consecutively,
and occupy those chairs. However, if there are not enough consecutive unoccupied chairs, they will
leave without taking seats.
Determine whether it is guaranteed that all N groups can take seats.
输入:
3 4
1 2 1
输出:
Yes
身为ARC的第一题难度本来应该是入门题,然而卡了我两个小时…
比赛刚开始,我看了一眼题,直接认为2的个数大于2肯定是不对的,因为我当时想只要有两个2肯定会交叉(然而这个思想肯定是错了).然后我室友提出了一个看似很正确的想法,就是序列最后一个数字如果是2的话,那肯定是不行的.诶,我当时推了一波,好像确实是这样,因为如果是1的话可以随便插,但是是2的话我们可以使用之前的1使其只能放在我们的首尾两端.
但是交上去之后还是wa,然后就一直陷入自闭之中,两个人一直推不出正确答案…
还剩半小时时,我找到了一个反例:2 2 2 1.然后我根据上述的理论加上了一个补丁,那就是末尾两个数和是3的话肯定是不满足的,但是打上补丁之后还是wa.然后就一直wa,最后一整场比赛爆零
赛后看了一下题解,发现我们在打这道题时一直有一个误区,那就是在到我们的最后几个数字之前可能就有组是无法坐下的…一直陷入了一个牛角尖中.所以正确的做法应该是正着做的…
总结一下感觉还是自己思维题打少了,对于这种思维题的解决还是有点问题.以后准备多打打AtCoder上的题目了
补上赛后写的正解
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;int a[maxn];int l;
int main() {n=read();l=read();for(int i=1;i<=n;i++) {a[i]=read();if(a[i]==2&&l<2) {cout<<"No"<<endl;return 0;}l-=(a[i]+1);}cout<<"Yes"<<endl;return 0;
}
