## tc-552-div2

2013年08月26日 ⁄ 综合 ⁄ 共 3612字 ⁄ 字号 评论关闭

250 题：

```/*

*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;

const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<30);

const double eps=1e-10;
const double pi=acos(-1.0);

#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))

template<class T> inline T gcd(T a,T b)//NOTES:gcd(
{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}

typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下，左下，左，左上，上，右上，右，右下。

//******* WATER ****************************************************************

//flag = 0，横；flag = 1,竖
int calc(vector <string> flowers, bool flag, int start, int end) {
int ret = 0;
if(start > end) return 0;
if(!flag) {
for(int j = 0; j < flowers[0].length(); j++) {
for(int i = start; i <= end; i++) {
if(flowers[i][j] == 'F') ret++;
}
}
}
else {
for(int i = 0; i < flowers.size(); i++) {
for(int j = start; j <= end; j++) {
if(flowers[i][j] == 'F') ret++;
}
}
}
return ret;
}

class FoxAndFlowerShopDivTwo {
public:
int theMaxFlowers(vector <string> flowers, int r, int c) {
int ret = 0, tmp;
tmp = calc(flowers, false, 0, r - 1);
ret = chmax(tmp, ret);
tmp = calc(flowers, false, r + 1, flowers.size() - 1);
ret = chmax(tmp, ret);
tmp = calc(flowers, true, 0, c - 1);
ret = chmax(tmp, ret);
tmp = calc(flowers, true, c + 1, flowers[0].length() - 1);
ret = chmax(tmp, ret);
return ret;
}
};

```

500:

1

2    3

3   1   2

1    2    3   1

2    3    1    2   3

3    1     2    3    1   2

1.所有的1,2,3中颜色的球的个数相同，这时候N%3 == 2；

2.所有的1,2,3中颜色1的多一个，颜色2和3的相同。颜色1的个数为ceil(sum/3),颜色2和3的个数为floor（sum/3)，其中sum = （N + 1) * N ;

RGB三种颜色最多各染r，g，b种，那么有两种情况：

1. r + g + b总数不够染色，限制染色数目，为:floor((r +g+b)/sum);

2.最少的颜色限制染色数目，floor(min_color / ceil(sum/3));其中min_color = min(r, g, b);

code：

```/*

*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;

const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<30);

const double eps=1e-10;
const double pi=acos(-1.0);

#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))

template<class T> inline T gcd(T a,T b)//NOTES:gcd(
{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}

typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下，左下，左，左上，上，右上，右，右下。

//******* WATER ****************************************************************

class FoxPaintingBalls {
public:
long long theMax(long long R, long long G, long long B, int N) {
LL minx = chmin(R, chmin(G, B));
LL tot = (N + 1) * N / 2;
LL one = tot / 3;
if(N == 1) return R+G+B;
return chmin((R+G+B) / tot, minx / one);
}
};