石家庄建站费用,太原营销型网站建设制作,嘉兴网站搜索排名,wordpress添加域名Description 乡间有一条笔直而长的路称为“米道”。沿着这条米道上 R 块稻田#xff0c;每块稻田的坐标均为一个 1 到 L 之间(含 1 和 L)的整数。这些稻田按照坐标以不减的顺序给出#xff0c;即对于 0 ≤ i R#xff0c;稻田 i 的坐标 X[i]满足 1 ≤ X[0] ≤ ... ≤ X[…Description 乡间有一条笔直而长的路称为“米道”。沿着这条米道上 R 块稻田每块稻田的坐标均为一个 1 到 L 之间(含 1 和 L)的整数。这些稻田按照坐标以不减的顺序给出即对于 0 ≤ i R稻田 i 的坐标 X[i]满足 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。 注意可能有多块稻田位于同一个坐标上。 我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样米仓将建在米道上其坐标也是一个 1 到 L 之间的整数含 1 和 L。这个米仓可以建在满足上述条件的任一个位置上包括那些原来已有一个或多个稻田存在的位置。 在收获季节每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓需要雇用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 1 元。換言之将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。 不幸的是今年预算有限我们至多只能花费 B 元运费。你的任务是要帮我们找出一个建造米仓的位置可以收集到尽可能多的稻米。 Input 第一行 三个整数 R L B接下来R行 每行一个整数 表示X[i] Output 一个整数 最多稻米数 Sample Input 5 20 6 1 2 10 12 14 Sample Output 3 HINT 1 ≤ R ≤ 100,000 1 ≤ L ≤ 1,000,000,000 0 ≤ B ≤ 2,000,000,000,000,000 解析其实去画一画或想一下就会发现米仓在两个稻田间的任意位置两个稻田的运费之和都相等那么我们不如直接考虑将它建在哪一块稻田上。 二分枚举稻田数x然后用一个for循环来枚举我们所假想收割的x个稻田中最左边的那个稻田位置为l,然后通过x推出r,mi最右边的位置和中间位置。谷仓在中间时为最优解这个自己去试试画出来想所以谷仓位置为mi。好啦那么我们枚举的这段区间的费用是多少呢可能很多人会和我一样第一反应是用一个for循环来计算可是之前的枚举已经是O(nlogn)了这就决定了我们的计算最好复杂度为O1。我们用前缀和来实现。首先设费用为sum,f为一个数组这个数组中f[i]储存的是1~i块稻田的坐标和a数组用来储存每块稻田的坐标设一个变量now来表示米仓的坐标就是a[now]则公式为 sumnow*(mi-l)-(f[mi-1]-f[l-1])(f[r]-f[mi])-now*(r-mi); 为什么这么做呢下面来解释一下。 我们需要把区间分成左右两边来做左边的费用等于now-a[l]now-a[l1]now-a[l2]....now-a[mi-1];我们可以发现他是有多个now-a[?]组合而成有几项呢不拿算出总共有mi-l(不是数字1是L项则式子变为now*(mi-l)-(a[l]a[l1]a[l2]....a[mi-1]);好啦那么a[l]..a[mi-1]即为第l块稻田到第mi-1块稻田的坐标之和完全可以用前缀和直接表示成f[mi-1]-f[l-1],好啦左边的式子最终成为now*(mi-l)-(f[mi-1]-f[l-1])同理右边的式子也可以这样推出来不写啦。 算出sum后只要比B元小就成立了否则不成立。 程序 #includeiostream
#includecstdio
using namespace std;
long long f[100010],now,k,ans,a[100010],sum,n,l,b,lef,righ,mid;
bool check(long long x)
{int i,l,r,mi;for (i1;in-x1;i){li;最左边的稻田 rix-1最右边的稻田; mi(lr)/2米仓;nowa[mi];米仓坐标sumnow*(mi-l)-(f[mi-1]-f[l-1])(f[r]-f[mi])-now*(r-mi);
式子的具体推法已经写在上面了if (sumb) return true;}return false;
}
int main()
{cinnlb;for (int i1;in;i) cina[i];f[0]0;for (int i1;in;i) f[i]f[i-1]a[i];前i个稻田的坐标之和lef0;righn1;ans0;while (lefrigh) 枚举有几块稻田能收割{mid(lefrigh)/2;if (check(mid)true) {lefmid1;if (ansmid) ansmid;}else righmid-1;} coutansendl;return 0;
} 好啦好啦。 转载于:https://www.cnblogs.com/2014nhc/p/6208118.html
