seerc 2014 A Banks (暴力)
题意:n个数围成一圈,对于负数可以进行magic操作,也就是取反,但是会影响到左右相邻的,加上这个负数。问最少进行多少次magic操作,使得所有数都是非负。
思路:我们知道,如果一个负数想变成整数的话,只能通过magic 操作。唯一可能影响次数的就是顺序。
不过手动写了几个发现顺序好像无关紧要?
于是大胆猜测,写了发暴力2333。
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int maxn = 1e4+10;
7int n,a[maxn];
8void work(){
9 queue<int> Q;
10 int cnt = 0;
11 while(!Q.empty())Q.pop();
12 for(int i = 0; i < n; i++){
13 if(a[i] < 0){
14 Q.push(i);
15 }
16 }
17 while(!Q.empty()){
18 int fr = Q.front();
19 Q.pop();
20 if(a[fr]>=0)continue;
21 int delta = -a[fr];
22 if(a[(fr+n-1)%n] - delta < 0){
23 Q.push((fr+n-1)%n);
24 }
25 if(a[(fr+1)%n] - delta < 0){
26 Q.push((fr+1)%n);
27 }
28 a[(fr+n-1)%n]-=delta;
29 a[(fr+1)%n]-=delta;
30 a[fr] = -a[fr];
31 cnt++;
32 }
33 printf("%d\n",cnt);
34}
35int main()
36{
37 //freopen("in.txt","r",stdin);
38 while(scanf("%d",&n)==1){
39 for(int i = 0; i < n; i++)scanf("%d",&a[i]);
40 work();
41 }
return 0;
}