hiho一下第216周《Gas Stations》题目分析

3
1

《Gas Stations》题目分析

这道题中已有的N个加油站是不能移动的，所以相当于把整条高速公路分成了N-1个区间。
并且由于每个区间的两端是固定的，所以每个区间中新建的加油站应该等距分布。比如在[2, 11]之间建2个加油站(2和11已经有加油站)，显然建在5和8的位置最优。
于是每个区间中新建的加油站的数量就决定了它们的位置，也决定了区间中两两加油站的距离。

在此基础上，这道题有两种做法。

第一种是贪心。我们考虑分成K次，每次增加一个加油站。那么新加的加油站应该处于哪个区间呢？ 显然应该处于“最稀疏”的区间，也就是两两距离最大的区间。

于是我们可以用堆来维护每个区间中加油站的“稀疏”程度，每次O(logN)选出最稀疏的区间，加入一个加油站，再重新计算稀疏度。总复杂度是O(KlogN)的。

第二种是二分答案。假设新建K个加油站的答案是F(K)，那么函数F(x)显然是单调递减的，也就是新建的加油站最多，答案越小。

于是我们可以用二分答案来求解。假设加油站之间的距离不少于d，那么我们可以根据d求出每个区间中最多新建多少加油站。如果总数小于K，说明答案比d小，否则说明答案不小于d。

直到二分的d的上下界之差足够小时，d即为答案。

  • 统计转换的时候不要用int强制转换，用ceil 血的教训

  • 添加评论
  • ✖reply

6 answer(s)

0

贴一个二分写法：

#include <bits/stdc++.h>
using namespace std;
int a[1010],n;
bool check(double x,int k){
    int now=0,dis;
    for(int i=1;i<n;i++){
        dis=a[i]-a[i-1];
        if(dis>x){
            if(x!=(int)x)now+=dis/x;
            else{
                if(dis%(int)x==0)now+=dis/x-1;
                else now+=dis/x;
            }
        }
        if(now>k)return false;
    }
    return true;
}
int main()
{
    int m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    double l=0,r=m,mid;
    while(r-l>1e-3){
        mid=(l+r)/2;
        if(check(mid,k))r=mid;
        else l=mid;
    }
    printf("%.1f",l);
    return 0;
}
0

一个失败的二分查值,试过许多例子没找到反例啊,可以帮忙看看吗?重新贴了一下代码

#include <stdio.h>
const int maxn=1001;
const int maxa=100005;
int n,m,k;
int a[maxn];
int dis[maxn];
bool c(int t){
    int num=0;
    for(int i=0;i<n-1;i++) num+=(dis[i]*100-1)/t; 
    return num<=k;
}
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n-1;i++) dis[i]=a[i+1]-a[i];

    int l=0,r=100*maxa,mid;
    for(int i=0;i<1000;i++){
        mid=(l+r)/2;
        if(c(mid)) r=mid; 
        else l=mid;
    }
    if(r%10>=5){//手动四舍五入 
        r=r-r%10;
        r+=10;
    }
    printf("%.1f",r*0.01);
}
int main(){
    solve();
    return 0;
}
0

一个失败的二分查值,试过许多例子没找到反例啊,可以帮忙看看吗?

#include <stdio.h>

const int maxn=1001; const int maxa=100005; int n,m,k; int a[maxn]; int dis[maxn];

bool c(int t){ int num=0; for(int i=0;i

void solve(){ scanf("%d%d%d",&n,&m,&k); for(int i=0;i 

int l=0,r=100*maxa,mid;
for(int i=0;i<1000;i++){
    mid=(l+r)/2;
    if(c(mid)) r=mid; 
    else l=mid;
}
if(r%10>=5){//手动四舍五入 
    r=r-r%10;
    r+=10;
}
printf("%.1f",r*0.01);

}

int main(){ solve(); return 0; }

0

第一种是贪心。我们考虑分成K次，每次增加一个加油站。那么新加的加油站应该处于哪个区间呢？ 显然应该处于“最稀疏”的区间，也就是两两距离最大的区间。

这样的贪心法真的可行吗？？ 减少总长 1000，已有三个煤气站，位置分别在0,998,1000。可以新增2两站点；； 贪心法的结果是不是： 先在0到999之间新增一个（位置499）； 再在0~499的中间，或者499~998的中间建一个； 但实际最短应该是在0~988的两个三分点上面各建一个使得结果最小。。

求解惑。。

  • 不是的,稀疏度的概念是对于原本的那n-1个段,就像样例输入 3 10 2 0 2 10 有两个段长度分别为2和8是吧,此时稀疏度就是2和8,我发现8最大,故而砍第二个段一刀,稀疏度变为2和4,4还是大,故而第二刀还是砍它,砍了之后稀疏度变为2和2.7,具体实现时可以用pair作为单位的大根堆来实现,first为稀疏度,second为原始段长,这样甚至不用重载比较规则,因为pair为单位时默认以first排序

  • 纠正一下我的话,second为原始段序号,最重要的就是要另外开一个数组length记录原始段长,再开一个num记录一下这n-1个段每个段被砍过几刀,之后通过出大根堆根节点,就能知道哪个段稀疏度最高,砍他,新的稀疏度就是 length[i]/(num[i]+1),将至重新压进大根堆,这样重复砍k刀

  • https://blog.csdn.net/qq_31964727/article/details/82343969 为这道题写了一个博客,可以参考一下,带ac代码

  • 添加评论
  • ✖reply
0

求大佬帮忙看看这个贪心哪里写错了

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 1e6 +10;
typedef struct no
{
    int dis,tot;
    double x;
}node;
bool operator <(no t,no t1)
{
    if(t.x==t1.x)
        return t.dis<t1.dis;
    return t.x<t1.x;
}
priority_queue<node> q;
int a[maxn];
int main(){
    //freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
    //freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    int n,m,k;
    cin>>n>>m>>k;
    node t;
    R(i,n)
    {
        cin>>a[i];
    }
    R(i,n-1)
    {
        t.dis=a[i+1]-a[i];
        t.tot=1;
        t.x=(t.dis*1.0)/t.tot;
        q.push(t);
    }
    if(a[0]!=0)
    {
        t.dis=a[0];
        t.tot=1;
        t.x=a[0]*1.0/t.tot;
        q.push(t);
    }
    if(a[n-1]!=m)
    {
        t.dis=m-a[n-1];
        t.tot=1;
        t.x=t.dis*1.0/t.tot;
        q.push(t);
    }
    for(int i=0;i<k;i++)
    {
        node t1=q.top();
        q.pop();
        t1.dis=t.dis;
        t.tot=t1.tot+1;
        t.x=t.dis*1.0/t.tot;
        q.push(t);
    }
    t=q.top();
    cout<<setiosflags(ios::fixed)<<setprecision(1);

    cout<<t.x<<endl;
    return 0;
}

  • for(int i=0;i<k;i++) { node t1=q.top(); q.pop(); t1.dis=t.dis; t.tot=t1.tot+1; t.x=t.dis*1.0/t.tot; q.push(t); } 这个地方和t没关系了吧，只用t1就可以了

  • 楼上正解。“if(a[0]!=0)” 和“if(a[n-1]!=m)”都没有必要写，题目已经说了这种情况不会发生。感觉你的代码是做梦写的，太飘逸了。

  • 添加评论
  • ✖reply
0

求一个用优先队列写的贪心代码 蒟蒻不怎么会重载里面的小于号

  • 两种写法1：写仿函数 struct node { int a,b; }; struct comp { bool operator()(node x,node y) { if(x.a==y.a) return x.b<y.b; else x.a<y.b; } }; priority_queue<comp> q;

  • 2.重载 struct node { int a,b; bool operator<(node &x) { if(x.a==a) return x.b<b; else x.a<a; } }; priority_queue<node> q;

  • https://blog.csdn.net/DongChengRong/article/details/82017702 这是用优先队列写的贪心代码

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲