一个长度为n的记账单，+表示存￥1，-表示取￥1。现在发现记账单有问题。一开始本来已经存了￥p，并且知道最后账户上还有￥q。你要把记账单修改正确，使得 1：账户永远不会出现负数； 2：最后账户上还有￥q。你有2种操作： 1：对某一位取反，耗时x； 2：把最后一位移到第一位，耗时y。
本文共 1981 字，大约阅读时间需要 6 分钟。
一个长度为n的记账单，+表示存￥1，-表示取￥1。现在发现记账单有问题。一开始本来已经存了￥p，并且知道最后账户上还有￥q。你要把记账单修改正确，使得 1：账户永远不会出现负数； 2：最后账户上还有￥q。你有2种操作： 1：对某一位取反，耗时x； 2：把最后一位移到第一位，耗时y。
The first line contains 5 integers n, p, q, x and y (1 n 1000000, 0 p;q 1000000, 1 x;y 1000), separated by single spaces and denoting respectively: the number of transactions done by Byteasar, initial and final account balance and the number of seconds needed to perform a single turn (change of sign) and move of transaction to the beginning. The second line contains a sequence of n signs (each a plus or a minus), with no spaces in-between. 1 ≤ n ≤ 1000000, 0 ≤ p ,q ≤ 1000000, 1 ≤x,y ≤ 1000)
修改消耗的时间
暴力枚举操作2，然后对于每种情况算一下操作1需要多少次求个最小值
枚举操作2相当于就是把序列当成一个环，然后枚举起点
主要在如何求操作1要多少次
首先算一下到底需要多少个'+'和多少个'-'，如果'-'少了就把最后面的若干个'+'改掉，
如果'+'少了就把最前面的如干个'-'改掉
之后再看会不会出现p+前缀和为负的情况，这里需要用优先队列先求出每个起点的最小前缀和
最小前缀和知道后，如果为负就需要将前面的'+'改成'-'，后面的'-'改成'+'
OK，最后求出最小值
#include#include #include using namespace std;#define LL long longdeque Q;char str[1000005];LL a[2000005], b[2000005], sum[2000005];int main(void){ LL n, p, q, x, y, i, ans, now; scanf("%lld%lld%lld%lld%lld%s", &n, &p, &q, &x, &y, str+1); for(i=1;i<=n;i++) a[i] = str[i]=='+'?1:-1; for(i=n+1;i<=n*2;i++) a[i] = a[i-n]; for(i=n*2;i>=1;i--) sum[i] = sum[i+1]+a[i]; n *= 2; for(i=n;i>=1;i--) { if(i<=n/2) b[i] = sum[i]-sum[Q.back()]; while(Q.empty()==0 && sum[Q.front()]<=sum[i]) Q.pop_front(); Q.push_front(i); while(Q.back()>=i+n/2) Q.pop_back(); } ans = 214748364721474847ll; n /= 2; for(i=1;i<=n;i++) { now = y*((n-i+1)%n); if(p+sum[n+1]>=q) now += (p+sum[n+1]-q)/2*x; else { now += (q-p-sum[n+1])/2*x; b[i] += (q-p-sum[n+1]); } if(p+b[i]<0) now -= (p+b[i]-1)/2*2*x; ans = min(ans, now); } printf("%lld\n", ans); return 0;}/*15 0 1 2 3+--++---++--+++15 5 0 1 1000----------+++++*/
转载地址：http://cqmgf.baihongyu.com/