2644: 烤干机 c++分治思想

解题思路:

这道题第一眼会想到全排列或者优先队列毫无疑问这是错的，因为时间复杂度太高了

所以我想的是分治算法（因为最近比较菜想了好久）

int f[500002];定义数组 int a(即A),b(即B)

首先我们对数组f[i]进行排序（sort排序方便简洁）

假设最优值为x

x属于到f[0]/a到f[n-1]/a+1;(因为f[n-1]%a可能不为0 同时也省去了判断是否整除的步骤)

故max=f[n-1]/a+1，min=f[0]/a;

设置中间值mid=(max+mid)/2;

然后缩小x所在的区间

当可以f[x]符合晒干条件切f[x-1]不符合晒干条件时mid为最优时间

当可以f[x]符合晒干条件切f[x-1]符合晒干条件时-->max=mid;

当可以f[x]不符合晒干条件切f[x-1]不符合晒干条件时-->min=mid+1;

晒干条件为这个函数（简单易懂）

bool fun(int mid)

{

int t;

for (int i = 1; i < n; i++)//晒掉在mid时刻小于0的值

{

if (f[i] > mid*a)

{

t = i;

break;

}

}

int sum = 0;

for (int i = t; i < n; i++)

大于0的值对b取余，并相除

//(f[i] - mid * a)表示在mid时刻剩余的湿度

//对b取余判断在(f[i] - mid * a)/b是否还有湿度剩余,若有剩余则取余不为0 需要多加一时刻

sum为剩余未干衣服所需要b点每小时烘干速度的总时长需要小于mid

{

if ((f[i] - mid * a) % b == 0)

{

sum = sum + (f[i] - mid * a) / b;

}

else

{

sum = sum + (f[i] - mid * a) / b+1;

}

}

if (sum<=mid)

{

return true;

}

else

{

return false;

}

}

我们可以直接得出mid就是时间
注意事项:

参考代码:

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

int f[500002];

int a, b;

int n;

bool fun(int mid)

{

int t;

for (int i = 1; i < n; i++)

{

if (f[i] > mid*a)

{

t = i;

break;

}

}

int sum = 0;

for (int i = t; i < n; i++)

{

if ((f[i] - mid * a) % b == 0)

{

sum = sum + (f[i] - mid * a) / b;

}

else

{

sum = sum + (f[i] - mid * a) / b+1;

}

}

if (sum<=mid)

{

return true;

}

else

{

return false;

}

}

int main()

{

cin >> n;

cin >> a >> b;

for (int i = 0; i < n; i++)

{

cin >> f[i];

}

sort(f, f + n);

bool sum = true;

int max1, mid, min1;

max1 = f[n - 1] / a+1;

min1 = f[0] / a;

mid = (max1 + min1) / 2;

while (sum)

{

if (fun(mid)&&!fun(mid-1))

{

sum = false;

}

else if(fun(mid) && fun(mid - 1))

{

max1 = mid;

mid = (max1 + min1) / 2;

}

else

{

min1 = mid + 1;

mid = (max1 + min1) / 2;

}

}

cout << mid << endl;

return 0;

}