[思维][预处理][贪心] codeforces 990E Post Lamps

连续做的又一道预处理+贪心的题目,一开始因为复杂度的原因一直没有下手,看了官方题解才意识到复杂度是nlogn,因为调和级数求和是logn。。。

贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点,如果这个点等于原来的出发点就直接return -1,因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点(也有可能是他自己),当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理,其次是复杂度的分析没有到位。

错误的点的话是对题意的理解:这里要求覆盖整条线段,而不仅仅是覆盖整点,但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了,原来的算法在这里会失效,因为那个总是多考虑一步,而没有考虑出发点是不是合法的。

#include 
#include 
#include
#include
#include
#include

using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const LL INF=(1LL<<60);//fuck

int pre[maxn];
bool block[maxn];
int cost[maxn];
int n;
LL cal(int k)
{
    int cur=0,nxt=0;
    LL ans=0;
    while(cur+k=n)
        ans++;
    return ans;
}

int main()
{
    int m,k;
    LL tmp;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&tmp);
        block[tmp]=1;
    }
    if(block[0])
    {
        cout<<"-1\n";
        return 0;
    }
    for (int i=1;i<=k;i++)
        scanf("%d",&cost[i]);
    for (int i=0;i<=n;i++)
    {
        if(!block[i])
        {
            pre[i]=i;
        }
        else
        {
            pre[i]=pre[i-1];
        }
    }
    LL ans=INF;
    for (int i=1;i<=k;i++)
    {
        tmp=cal(i);
        if(tmp!=INF)
            ans=min(ans,tmp*cost[i]);
    }
    if(ans==INF)
        cout<<"-1"<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据