首页 > 代码库 > （模拟+贪心）codeforces - 733C Epidemic in Monstropolis
（模拟+贪心）codeforces - 733C Epidemic in Monstropolis
题意：有一排数字，大的数字向左或者向右吃相邻的比它小的数字，问能不能吃成另一个数列。
分析：
稍微想一下，可以感觉得到，新数列的每个数字都是由一段连续的原数列子数列相互吃成的，并且这些子数列也是从头连续的相连的，进而组成的原数列。比如
a[0] [1] [2] [3] [4]
b[0] [1]
如果b[0]==a[0]+a[1]+a[2]，那么b[0]就是a[0-2]吃成的。
那么如果YES，必然b[1]==a[3]+a[4]，也就是b[1]是由a[3-4]吃成的。
所以只需要先找出满足的子数列，在寻找的过程中，找出满足条件的每个子数列，再分别再每个子数列中选择最大的向左向右吃贪心。
但是NO有很多坑点：
1、a前面的几个数已经匹配完了b中所有的数，且a还有剩余，必然NO（在这WA了2发）
2、单独的一个匹配（子数列中每个数一样大当且仅当子数列的长度大于1，才能是NO）的时候应该是YES
这题好坑啊，WA了五六发。。。曹。。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <vector> 5 #include <map> 6 #include <set> 7 #include <queue> 8 #include <cstring> 9 #include <algorithm> 10 11 using namespace std; 12 13 14 typedef long long ll; 15 typedef unsigned long long ull; 16 #define inf (0x3f3f3f3f) 17 #define lnf (0x3f3f3f3f3f3f3f3f) 18 #define eps (1e-8) 19 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1 ;} 20 21 //------------------------------------------------- 22 23 const int maxn=510; 24 int an[maxn],bn[maxn]; 25 vector<int> v[maxn]; 26 27 char ac[maxn]; 28 int as[maxn]; 29 30 void solve(){ 31 int a,b; 32 scanf("%d",&a); 33 for(int i=0;i<a;i++){ 34 scanf("%d",&an[i]); 35 } 36 scanf("%d",&b); 37 for(int i=0;i<b;i++){ 38 scanf("%d",&bn[i]); 39 } 40 int cnt=0; 41 int res=0; 42 int st=0; 43 for(int i=0,j=0;i<b,j<a;j++){ 44 res+=an[j]; 45 if(res==bn[i]){ 46 for(int k=st;k<=j;k++){ 47 v[cnt].push_back(an[k]); 48 } 49 cnt++; 50 st=j+1; 51 res=0; 52 i++; 53 } 54 if(cnt==b&&j<a-1){ 55 puts("NO"); 56 return; 57 } 58 } 59 if(cnt!=b){ 60 puts("NO"); 61 return; 62 } 63 int num=0; 64 for(int i=0;i<cnt;i++){ 65 int maxs=-1; 66 int site; 67 for(int j=0;j<v[i].size();j++){ 68 if(j==0){ 69 if(v[i][j]>maxs&&v[i][j+1]<v[i][j]){ 70 maxs=v[i][j]; 71 site=j; 72 } 73 } 74 else if(j==v[i].size()-1){ 75 if(v[i][j]>maxs&&v[i][j-1]<v[i][j]){ 76 maxs=v[i][j]; 77 site=j; 78 } 79 } 80 else{ 81 if(v[i][j]>maxs&&(v[i][j]>v[i][j-1]||v[i][j]>v[i][j+1])){ 82 maxs=v[i][j]; 83 site=j; 84 } 85 } 86 } 87 if(maxs==-1&&v[i].size()>1){ 88 puts("NO"); 89 return; 90 } 91 int si=v[i].size(); 92 while(si>1){ 93 if(site==0){ 94 if(v[i][site]>v[i][site+1]){ 95 ac[num]=‘R‘; 96 as[num++]=site+i; 97 for(int j=site+2;j<si;j++){ 98 v[i-1]=v[i]; 99 }100 v[i][site]+=v[i][site+1];101 si--;102 }103 }104 else if(site==si-1){105 if(v[i][site]>v[i][site-1]){106 ac[num]=‘L‘;107 as[num++]=site+i;108 site--;109 v[i][site]+=v[i][site+1];110 si--;111 }112 }113 else{114 if(v[i][site]>v[i][site+1]){115 ac[num]=‘R‘;116 as[num++]=site+i;117 for(int j=site+2;j<si;j++){118 v[i-1]=v[i];119 }120 v[i][site]+=v[i][site+1];121 si--;122 }123 else if(v[i][site]>v[i][site-1]){124 ac[num]=‘L‘;125 as[num++]=site+i;126 site--;127 v[i][site]+=v[i][site+1];128 si--;129 }130 }131 }132 133 }134 puts("YES");135 for(int i=0;i<num;i++){136 printf("%d %c\n",as[i]+1,ac[i] );137 }138 139 140 141 }142 143 144 145 int main(){146 147 #ifndef ONLINE_JUDGE148 freopen("1.in","r",stdin);149 //freopen("1.out","w",stdout);150 #endif151 152 solve();153 }
（模拟+贪心）codeforces - 733C Epidemic in Monstropolis
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。