二分出可能的值
对于每个 min 去判断是否可行
用贪心去判断 首先numa = 0
首先 i = j = 1 表明当前选择第j 到 i 行（j >= i）
然后去判断这几行是否能分成B块 如果大于等于B那么numa++;j++,i = j 不行的话就j++
最后numa >= A 就说明mid成立
[
html]
#include
const int MAX = 510;
int n,m,A,B;
int a[MAX][MAX];
int map[MAX][MAX];
bool check(int mid)
{
int numa = 0,numb = 0,sum;
int i = 1,j = 1,k;
while(j <= n)
{
numb = 0;
sum = 0;
for(k = 1; k <= m; k++)
{
sum += map[j][k] - map[i-1][k];
if(sum >= mid)
{
numb ++;
sum = 0;
}
}
if(numb >= B)
{
i = j+1;
j++;
numa++;
}
else
j++;
}
if(numa >= A)
return true;
return false;
}
int main()
{
int i,j,sum,l,r,mid;
scanf("%d %d %d %d",&n,&m,&A,&B);
{
r = 0;
sum = 0;
for(i = 1; i <= n; i++)
{
for(j = 1;j <= m; j++)
{
scanf("%d",&a[i][j]);
map[i][j] += map[i-1][j] + a[i][j];
sum += a[i][j];
}
}
l = 0;
r = sum / (A*B);
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid))
l = mid + 1;
else
r = mid - 1;
}
printf("%d\n",r);
}
return 0;
}
Tree Decoration
深搜吧 搜到底 然后把子树里面最小装饰一个物品的时间的存下来 回溯的时候判断以每个节点为根的子树 如果当前子树不够 就用它
[html]
#include
#include
#define MAX 100010
using namespace std;
struct node
{
__int64 x;
__int64 num;//需要的个数
__int64 t;//需要的时间
__int64 min;//子树中的最短时间
__int64 sum;//子树的个数
__int64 time;//子树的时间
}a[MAX];
__int64 n;
vector v[MAX];
void dfs(__int64 u)
{
__int64 temp = 0x7fffffff,sum = 0,sumt = 0;
__int64 i;
__int64 len = v[u].size();
for(i = 0;i < len; i++)
{
dfs(v[u][i]);
if(temp > a[v[u][i]].min)
temp = a[v[u][i]].min;
sum += a[v[u][i]].sum;
sumt += a[v[u][i]].time;
}
if(temp > a[u].t)
temp = a[u].t;
a[u].min = temp;
if(sum < a[u].num)
{
sumt += (a[u].num - sum)*a[u].min;
sum = a[u].num;
}
a[u].sum = sum;
a[u].time = sumt;
//printf("%d %d %d\n",u,sum,sumt);
}
int main()
{
__int64 i,x,y,z;
scanf("%I64d",&n);
for(i = 1;i <= n; i++)
{
scanf("%I64d %I64d %I64d",&x,&y,&z);
if(x != -1)
v[x].push_back(i);
a[i].x = x;
a[i].num = y;
a[i].t = z;
}
dfs(1);
printf("%I64d\n",a[1].time);
return 0;
}
Meeting Place
Package Delivery
迪杰斯特拉 优先队列优化
[html]
#include
#include
#include
#define MAX 50010
using namespace std;
struct node
{
int x,dis;
friend bool operator < (node a,node b)
{
return a.dis > b.dis;
}
};
vector v[MAX];
int dis[MAX];
bool vis[MAX];
int n,m;
void dijkstra(int start)
{
int i;
node no;
for(i = 0;i <= n; i++)
{
dis[i] = 0x7fffffff;
}
dis[start] = 0;
priority_queue q;
no.x = start;
no.dis = 0;
q.push(no);
while(!q.empty())//用优先队列省去了for循环去找最短的一条边
{