解题思路:
这道题第一眼会想到全排列或者优先队列毫无疑问这是错的,因为时间复杂度太高了
所以我想的是分治算法(因为最近比较菜想了好久)
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;
}
0.0分
3 人评分
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:621 |
C二级辅导-进制转换 (C语言代码)浏览:813 |
三进制小数 (C++代码)(第11位大于1.5才能进位)浏览:1151 |
C语言训练-排序问题<2> (C++代码)(sort函数)浏览:1579 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:720 |
C二级辅导-计负均正 (C语言代码)浏览:581 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:794 |
C二级辅导-等差数列 (C语言代码)浏览:1216 |
钟神赛车 (C语言代码)浏览:878 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1533 |