codeforce#378C. Epidemic in Monstropolis(模拟+分块+树状数组)

2016-12-14 09:53:15来源:http://blog.csdn.net/Rain722/article/details/53012368作者:Rain722人点击

第七城市
C. Epidemic in Monstropolistime limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard output


There was an epidemic in Monstropolis and all monsters became sick. To recover, all monsters lined up in queue for an appointment to the only doctor in the city.



Soon, monsters became hungry and began to eat each other.



One monster can eat other monster if its weight isstrictly greaterthan the weight of the monster being eaten, and they stand in the queue next to each other. Monsters eat each other instantly.
There are no monsters which are being eaten at the same moment. After the monsterAeats the monsterB,
the weight of the monsterAincreases by the weight of the eaten monsterB.
In result of such eating the length of the queue decreases by one, all monsters after the eaten one step forward so that there is no empty places in the queue again. A monster can eat several monsters one after another. Initially there werenmonsters
in the queue, thei-th of which had weightai.



For example, if weights are[1, 2, 2, 2, 1, 2](in order of queue, monsters are numbered from1to6from
left to right) then some of the options are:

the first monster can't eat the second monster becausea1 = 1is
not greater thana2 = 2;
the second monster can't eat the third monster becausea2 = 2is
not greater thana3 = 2;
the second monster can't eat the fifth monster because they are not neighbors;
the second monster can eat the first monster, the queue will be transformed to[3, 2, 2, 1, 2].


After some time, someone said a good joke and all monsters recovered. At that moment there werek(k ≤ n)
monsters in the queue, thej-th of which had weightbj.
Both sequences (aandb)
contain the weights of the monsters in the order from the first to the last.



You are required to provide one of the possible orders of eating monsters which led to the current queue, or to determine that this could not happen. Assume that the doctor didn't make any appointments while monsters were eating each other.

Input


The first line contains single integern(1 ≤ n ≤ 500)—
the number of monsters in the initial queue.



The second line containsnintegersa1, a2, ..., an(1 ≤ ai ≤ 106)—
the initial weights of the monsters.



The third line contains single integerk(1 ≤ k ≤ n)—
the number of monsters in the queue after the joke.



The fourth line containskintegersb1, b2, ..., bk(1 ≤ bj ≤ 5·108)—
the weights of the monsters after the joke.



Monsters are listed in the order from the beginning of the queue to the end.

Output


In case if no actions could lead to the final queue, print "NO" (without quotes) in the only line.



Otherwise print "YES" (without quotes) in the first line. In the nextn - klines print actions in the chronological order.
In each line printx— the index number of the monster in the current queue which eats and, separated by space, the symbol 'L'
if the monster which stays thex-th in the queue eats the monster in front of him, or 'R'
if the monster which stays thex-th in the queue eats the monster behind him. After each eating the queue is enumerated again.



When one monster eats another the queue decreases. If there are several answers, print any of them.

Examplesinput
6
1 2 2 2 1 2
2
5 5
output
YES
2 L
1 R
4 L
3 L
input
5
1 2 3 4 5
1
15
output
YES
5 L
4 L
3 L
2 L
input
5
1 1 1 3 3
3
2 1 6
output
NO

Note


In the first example, initially there weren = 6monsters, their weights are[1, 2, 2, 2, 1, 2](in
order of queue from the first monster to the last monster). The final queue should be[5, 5]. The following sequence of eatings leads to the
final queue:

the second monster eats the monster to the left (i.e. the first monster), queue becomes[3, 2, 2, 1, 2];
the first monster (note, it was the second on the previous step) eats the monster to the right (i.e. the second monster), queue becomes[5, 2, 1, 2];
the fourth monster eats the mosnter to the left (i.e. the third monster), queue becomes[5, 2, 3];
the finally, the third monster eats the monster to the left (i.e. the second monster), queue becomes[5, 5].


Note that for each step the output contains numbers of the monsters in their current order in the queue.


题意:



有n个怪物排成一列,如果一个怪物的体重严格大于和他相邻的怪物,那么可以吃掉那个怪物并更新队伍(即每个怪物的下标),之后怪物的体重变成两者之和,然后让你找出一种方案使得a序列可以变成b序列



分析:



(一).



前缀和的处理:



1.要合成k个,首先要将n个ai分成k份区间,而且每个区间的和要等于bi。



2.因为怪物只能吃相邻的,如果前缀和不能满足a[1]+a[2]+a[x]=b[1],a[x+1]+……+a[y]=b[2],……
那么就肯定不行


3.然后我们来看一段序列(即区间a[i]...a[i+num])满足什么条件才能合并成一个b(该区间和为b)


条件是:该序列中元素不完全一样,如果一样还怎么吃呢?



4.这段区间最大值为x,那么必然会有一个x和小于他的数相邻,



接下去,这个x就可以吃完序列中所有数完成合并.但是如果遇到有几个连续相同的最大值时要稍微考虑一下,找旁边有比他小的数的最大值。



(二)



输出路径的方法:



1.在上面的处理中,去记录每个区间的起始点和结束点,并记录每个区间内吃其他怪物的怪物(简称king)的下标,因为每个区间内的怪物都是由king来吃的(king吃了其他的怪物还是king),所以需要想方法来看他每一步怎么走,向左还是向右。



2.接下来就是去处理每段区间了,既然已经知道了每段区间的起始点和终点还有king。那么难点就是在处理吃的过程中怪物的下标变化了。如果某个怪物被吃掉,那么它身后的怪物就都得往前挪一个位置。这里用了下树状数组,向上更新,向下查询,即哪个怪物被吃更新一下树状数组C,C记录的是当前怪物需要向前挪动几位。那么每次位置就是当前位置i-C[i]了。


具体细节代码中会有详细注释:




#include
using namespace std;
const int maxn = 510;
int a[maxn], sum[maxn], b[maxn], index[maxn], king[maxn];//a数组记录原本怪物重量,sum是前缀和,b是合并区间后的怪物重量,index记录的是每个区间的左右端点,king记录每个区间的king下标
int C[maxn];
bool book[maxn];//记录哪些怪物被吃掉过
int lowbit(int lo)
{
return lo & (-lo);
}
void modify(int pos)
{
while(pos < 505)
{
C[pos] += 1; //每次当前怪物被吃,后面的怪物就往前移动一位,体现在树状数组上就是C[pos]++
pos += lowbit(pos);
}
}
int getsum(int pos)
{
int sum = 0;
while(pos > 0)
{
sum += C[pos];
pos -= lowbit(pos);
}
return sum;
}
bool getking_and_judge(int left, int right, int id)
{
int same = 1, ma = a[left]; //same记录区间内的元素有几个相同,ma为区间内的最大值,初始化为最左边的
king[id] = left; //当前区间内的king的下标的初始化
for(int i = left; i <= right; i++)
{
if(i > left && a[i] == a[left])
{
same++;
if(same == right - left + 1) //如果相同的个数等于区间内元素个数,那就是NO
return false;
}
if(i >= left + 1 && i <= right -1)
{
if((a[i-1] < a[i] || a[i+1] < a[i]) && a[i] >= ma) //更新ma和king的id的过程,即king的两边有一个比它重量小就可以
{
ma = a[i];
king[id] = i;
}
}
}
if(right - left >= 1 && a[right] > a[right-1] && a[right] >= ma) //特盘下区间的最右边能不能是king
{
king[id] = right;
}
return true;
}
void print(int left, int right, int id)
{
int kings_index = king[id]; //当前区间king的下标
int cou = right - left + 1; //区间内的元素个数,需要输出的步数即为cou-1
int cnt = 0, l = kings_index, r = kings_index, now; //用l和r从king的左右两边去寻找下一个吃哪个。
if(kings_index - 1 >= left)
l = kings_index - 1;
if(kings_index + 1 <= right)
r = kings_index + 1;
while(cnt < cou -1)
{
if(a[l] <= a[r] && !book[l])
{
now = kings_index - getsum(kings_index); //now即为怪物坐标变化后的坐标
printf("%d L/n", now);
book[l] = true; //现在的l是怪物达到的位置,标记一下
a[l] += a[kings_index]; //把重量合并一下
modify(kings_index + 1); //更新一下树状数组
kings_index = l; //更新一下king的下标,注意很重要因为上面的now有用到
if(l - 1 >= left) //把寻找用的l更新一下
l--;
}
else
{
now = kings_index - getsum(kings_index);
a[r] += a[kings_index];
printf("%d R/n", now);
book[r] = true;
modify(kings_index + 1);
kings_index = r;
if(r + 1 <= right)
r++;
}
cnt++; //步数+1
}
}
int main()
{
int n, k;
while(cin >> n)
{
memset(sum, 0, sizeof(sum));
memset(C, 0, sizeof(C));
memset(book, false, sizeof(book));
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i]; //前缀和的处理过程
}
scanf("%d", &k);
int sumb = 0;
for(int i = 1; i <= k; i++)
{
scanf("%d", &b[i]);
sumb += b[i]; //记录b的总和
}
if(sumb != sum[n]) //如果b的总和与之前所有怪物重量不相等,直接输出NO即可
{
printf("NO/n");
continue;
}
int pre = 0, cnt = 0; //pre是每个左边的起始点-1,cnt是记录有多少个区间,index数组中的每个下标除了第一个一位既是前一段区间的终点也是后一段区间的起始点
index[cnt] = 0;
for(int i = 1; i <= n; i++)
{
if(sum[i] - sum[pre] == b[cnt+1]) //通过前缀和只差来查看哪段区间的和与b[cnt+1]相等,因为b的下标是从1开始的,所以是cnt+1
{
index[++cnt] = i;
pre = i; //更新每个起始点
}
}
if(cnt != k) //如果不能划分出k个区间,就输出NO
{
printf("NO/n");
continue;
}
int Begin = 1, End, flag = 0; //到现在为止还没有判断过每个区间内的书是否一样,所以flag标记为0,Begin即为每个区间的起点,End为终点
for(int i = 1; i <= cnt && flag == 0; i++)
{
End = index[i];
if(!getking_and_judge(Begin, End, i)) //去判断区间内的怪物体重是否一样,另外获得king的下标
{
printf("NO/n"); //如果区间内的元素都一样就输出NO
flag = 1; //标记一下flag
break;
}
Begin = End + 1;
}
if(flag) //如果某一区间内的元素都一样就退出即可
continue;
Begin = 1; //Begin重新置为1
printf("YES/n");
for(int i = 1; i <= cnt; i++) //模拟出每个区间的输出路径
{
End = index[i];
print(Begin, End, i); //参数为区间起始点.终点和当前是第几个区间
Begin = End + 1;
}
}
return 0;
}



第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台