首页 > 代码库 > CodeForces 698A Vacations
CodeForces 698A Vacations
题目链接 : http://codeforces.com/problemset/problem/698/A
题目大意:
阿Q有n天假期,假期中有三种安排 休息、健身、比赛。每天有三种选择条件:
0 健身房不开门 没有比赛
1 健身房不开门 有比赛
2 健身房开门 没有比赛
3 健身房开门 有比赛
请给阿Q 合理的安排他的假期【阿Q不能连着两天健身或者连着两天比赛】,使得阿Q的休息天数最少。
解题思路:
ans=n,最多休息ans天
第一天是3 则a[0]=0,ans--;
只要是 a[0]>0,则 ans--;
从第二天开始在以后的每天里:
如果当天是 1 则判断前一天是不是1
1: 使当前a[i]=0,今天休息。
!1:昨天必定锻炼,ans--。
如果当天是 2 则判断前一天是不是2
2: 使当前a[i]=0,今天休息。
!2:昨天必定比赛,ans--。
如果当天是 3 则进行重点判断
如果昨天 为 1 则 今天 a[i]=2 ans--;
如果昨天 为 2 则 今天 a[i]=1 ans--;
如果昨天 为 0 则 今天任意做 a[i]=0 ans--; //*重点*
0不用判断 反正是休息 ans 保持不变。
举例:
7
1331123
1 ans--; 3 ans--,a[i]=2; 3 前一天为2 ans--,a[i]=1;1 前一天为1 休息a[i]=0;1 前一天为0 ans--;2 前一天为1 ans--;3 前一天为2,a[i]=1 ans--;
结果:ans=1。
AC Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int n; 6 while(~scanf("%d",&n)) 7 { 8 int ans=n,flag=0,a[n+2]; 9 for(int i=0; i<n; i++)10 scanf("%d",&a[i]);11 if(a[0]>0)ans--;12 if(a[0]==3)a[0]=0;13 for(int i=1; i<n; i++)14 {15 switch(a[i])16 {17 case 1:18 if(a[i-1]!=1)ans--;19 else a[i]=0;20 break;21 case 2:22 if(a[i-1]!=2)ans--;23 else a[i]=0;24 break;25 case 3:26 if(a[i-1]==1)a[i]=2,ans--;27 else if(a[i-1]==2)a[i]=1,ans--;28 else if(a[i-1]==0)a[i]=0,ans--;29 break;30 }31 }32 cout<<ans<<endl;33 }34 return 0;35 }
CodeForces 698A Vacations
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。