标签存档：贪心

【Link】http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1705

【题目大意】

n个数，你每次可以取<=3个数出来将他们都-1。然后放回去。问将所有数变为0至少需要多少次操作。

输出的两个数中第二个数是Sum

【算法】

lcc大神一下就秒杀了。我完全YY不出来。

 

first of all，每次取最大的3个出来减这种贪心是肯定没问题的。

但是数目太多了。

考虑每次都只能将一个数-1。

所以答案至少是最大那个数。

设m1是最大那个数，m2是次大那个数。

那么看看m1什么时候会将答案卡住。

很容易想到就是每次m1都减，减到最后的情况。然后看剩下的2个名额怎么去减。

用这两个名额，

要么是m2把这个名额卡住了，

要么减到最后剩下一个1，

要么是除了m1全部减为0。

 

(原因可以模拟一开始的贪心看看)

 

后面两种就判一下是不是Sum-m1<=m1*2就可以了。

第一种的卡住，只能发生在m2一直减，减到最后的情况，所以就是Sum-m1-m2<=m2。

 

答案被卡住的情况解决了，剩下的就是没被卡住的情况。

这些情况的答案都是Sum/3向上取整。

还是参见一开始的贪心，现在假设n>3(n<=3必然是答案是m1)每次我们都选最大的3个减。最后因为不会再被m1卡住了。设这些数中最小值为min，容易必然能够转到下面3种情况中的一种。

1、所有数都=min

2、2个数=min，其余数=min+1

3、1个数=min，其余数=min+1

转化为这个以后、、不断的3个3个减。。。很容易知道最后要么刚好减完，要么剩一个1，要么剩2个1。因为都是3个3个减，所以就和它% 3的结果有关系。。。于是就是Sum/3向上取整了= =

【其它】

Orz lcc大神

【CODE】

#include

#include

#include

#include

using namespace std;

 

int main(){

    int Tc,n;

    int a[1005];

    scanf("%d",&Tc);

    for (int k=1;k<=Tc;k++){

        scanf("%d",&n);

        for (int i=0;i

          scanf("%d",&a[i]);

        sort(a,a+n);

        int Sum=0,ans;

        for (int i=0;i

        if (n<=3) ans=a[n-1];

        else

            if (Sum-a[n-1]-a[n-2]<=a[n-2])

                ans=a[n-1];

            else

                if ( Sum-a[n-1]<=a[n-1]*2 )

                  ans=a[n-1];

                else ans=(Sum+2)/3;

        printf("Case #%d: ",k);

        printf("%d %dn",ans,Sum);

    }

}

【题目链接】http://www.codeforces.com/problemset/problem/3/B

【题目大意】

给定一个容量为v<=10^9的背包和n<=10^5个物品。

每个物品有一个体积(1<=ti<=2)和价值(1<=pi<=10^4)。

每个物品只能装一次，问最多能装多少价值的东西。

【算法分析】

一开始看的时候2了一下。。。还想到把体积为1的和成体积为2的然后根据奇偶性讨论一下。

然后后来重新一想发现实在太2了。

就是把体积为1和体积为2的放进两个数组里面，然后按价值从大到小排序。

然后用两个指针利用单调性维护可以很容易得出当取i个体积为1的物品时，答案最大能是多少。

于是就解决了。

【其它】

用桶排可以做到总复杂度O(n)

【CODE】

http://xiudaima.appspot.com/code/detail/4348006

【题目大意】

给定一个N*M(N,M<=500)的矩阵，矩阵中每一个格子都有一个权值。

1、只有第一行的格子能够建蓄水厂。

2、若与该格子有公共边的格子已经建有水利设施，并且这个建有水利设施的格子的权值大于该格子的权值，那么该格子可以建一个输水站。

问：能否使最后一行所有的点都建上水利设施？若能，则输出最少建多少个蓄水厂可以达到要求。若不能，则输出最后一行有多少个格子无法建立水利设施。

【算法分析】

首先注意到两个性质。

1、假设i,j都为第一行建蓄水厂的位置，那么他们供给最后一行的水利设施的配对关系可以不交叉。

如图：

若交叉，那么i必然能控制j现在控制的点。于是反证得该性质正确。

2、假设最后一行的每个点都能被覆盖，那么对于第一行的每一个结点，它所能控制最后一行的位置必然是连续的。

如图：

若不连续，根据性质1可知，其它点也无法覆盖红色部分，于是与“有解”这一前提矛盾，反证得该性质正确。

得出这两个性质以后解法就呼之欲出了。

首先把所有第一行的结点放入队列之中，进行广度优先搜索，然后可以看最后一行有多少个点被扩展到，从而得出是否有解以及有多少个点无法被覆盖到。

下面处理有解的情况。

对于每一个点，建立两个项L[i][j],R[i][j]，表示从这个点流出去，能覆盖到最后一行的最左端点及最右端点。

那么怎么快速处理得出所有点的L[i][j]及R[i][j]呢？

我们初始化所有L[N][i]=i , R[N][i]=i。

然后扩展开去影响其他的点。

笔者认为扩展有两类比较好的方法：

1、这个过程比较类似于最短路的扩展，所以SPFA或者Dijkstra+Heap都是不错的选择。使用它们的时间复杂度分别是O(kNM)、O(NM lg NM)

2、这个图显然是有向无环图，我们可以对它拓扑排序，然后按拓扑序扩展。这样做的时间复杂度O(NM)。或者说更直接一点按所有点的权值排序，然后按权值从小到大的顺序扩展。这样做的时间复杂度是O(NM lg NM)。

处理出所有的L[i][j]以及R[i][j]以后，问题就转化为：用最少的第一行的区间覆盖[1,M]这段所有的点。

令L’[i]=L[1][i]，R’[i]=R[1][i]。

我们按L’[i]把第一行的区间排序以后，就可以使用一个简单的贪心算法在O(M)的复杂度内解决这个问题。

这个贪心的C++代码如下，其中Q[i].L等价于L’[i],Q[i].R等价于R’[i]：

               int MaxR=0,ans=0,tmp;

               i=1;

               while (MaxR

                     tmp=MaxR;

                     while (i<=m && Q[i].L<=MaxR+1)

                       tmp=max(tmp,Q[i++].R);

                     MaxR=tmp;

                     ans++;

               }

               printf("%dn",ans);

【复杂度分析】

综上，我们如果在扩展时使用拓扑排序，那么可以做到

O(NM+M lg M)的时间复杂度 (这已经和读入数据所必须耗费的时间差不多了)

O(NM       )的空间复杂度

这两题本质是一样的，然后前者可以用匹配水过，于是成为NOIP模拟题的一部分。

后者必须严格n^2。

具体围观班长的解题报告~

然后LJN神牛搞了个n lg n AC了，不过暂时没有证明。膜拜~~~~

C++ CODE   :Tyvj1348 清理内奸 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798 #include C++ CODE   :BZOJ2034 [2009国家集训队]最大收益 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 #include

【题目大意】
一开始主角有一个能力值L，然后有n天，每天他可以执行下列两个操作中的其中一个：
1：自身能力值+1
2：制造与自己能力值相等个单位的食物。
另外，每天食物都会被饿鬼吃掉一些，但是主角又不能惹怒这个饿鬼。
求在不惹怒这个饿鬼的情况下，最后剩余食物最多能是多少？
如果必须惹怒，那么输出Myon。
【算法分析】
下面的 1 2分别表示操作1和操作2。
本题可以利用贪心来解决。
我们的策略应该是尽量升级，然后必须造食物才造。就是升级的尽量前推。
因为如果出现 2,1这种情况，而1和2可以交换而使得没有出现饿鬼被惹怒的情况，那么显然交换以后能造多一个单位的食物。所以升级是应该被尽量前推的。
可以发现其实我们是将这个操作分组，分成这样的数段：（1,2,2…2）,（1,2,2…..2）,（1,2,2….2)
（一开始在0天时我们看做操作1）
现在我们只关心操作1的划分。
为了实现我们的策略，那么我们对于前i天，都求出最多所能进行操作1多少次。
这可以用一个栈来解决。
这个栈里面存的是每次操作1所发生的时间。
然后每次把今天是操作1放进栈内。
如果栈尾的元素到今天不能满足饿鬼的需求，那么退栈，
这样我们维护的一个栈是所有升级操作都尽量前推好的了。并且到了第i天所能升级最多次的。
当然，如果栈里连第0天那个虚拟的升级都被退了，那么就无解了。
、
、
、
、
现在可能还有一些疑问，那就是升级多了固然会把饿鬼惹怒，但是有时候升级少了我们也会把饿鬼惹怒的。
比如说一开始能力值为0，然后你造食物多少天也没用。这样还是会惹怒饿鬼。
就是说，不能保证退栈以后依然是可行解。
、
、
、
、
现在我们再来看看一个东西。
假如说，我们退栈导致某个地方饿鬼不爽了。
那么我们从这个饿鬼不爽的地方分开来看。
假设饿鬼不爽这一天为j。
对于我们现在的第i天来讲，我们在第j天时，退栈前，能力强，剩余的食物也多。
（因为栈的大小代表升级的次数，并且原来饿鬼在第j天时爽的，退栈以后不爽，可以说明剩余食物变少了）
那么既然这样，如果会使得该解退栈后成为非可行解的，对于第i天来讲，是有害无利。
但是退栈的条件是升级这么多不行了。
所以，其实如果走出了这一步退栈，实际就是无解了。
我们会一直退到栈空为止。判为无解。
、
、
、
、
做完了第n天以后，我们还要把所有元素退栈，因为到了后面可能造食物更为划算。
然后这里退栈造成的非可行解问题，我们上面已经说明，如果是造成了非可行解，那么答案只会更差。
而我们取的最优值，所以一起判断也没关系。
然后，我们就得出了这个O(n)的贪心算法。
【其它】
泪流满面，3Y。原因是这个ZOJ的int64。。。居然这么标准，和NOI一样用long long+%lld。。。一开始就搞%I64d。搞挂了。
其实一开始我是看了一下月赛的Ranklist，发现最后一题好像每个人都A了。。。
然后想去切一下准备NOIP。。。
切了好一会儿终于切掉该题，感觉怎么现在的人都这么强T_T，这种题成为众人秒杀类题目。
颓然发现，由于题目过多，他那个Ranklist在我的浏览器下，下面还有横条。原来我看到众人秒杀的是倒数第二题。。。而最后一题只有navi大神AC。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const lld N=100005;
lld n,init_L,Qt;
lld a[N],Q[N],Rest_Food[N];
lld Sum[N];

int main(){
while (scanf("%lld%lld",&n,&init_L)!=EOF){
lld i,j,ans;
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
for (Sum[0]=0,i=1;i<=n;i++) Sum[i]=Sum[i-1]+a[i];
Qt=Rest_Food[0]=Q[0]=0;
for (i=1;i<=n;i++){
Qt++;
Q[Qt]=i;
Rest_Food[Qt]=Rest_Food[Qt-1]+(init_L+Qt-1)*(i-Q[Qt-1]-1)-(Sum[i]-Sum[Q[Qt-1]]);
while (Qt>=0 && Rest_Food[Qt]+(i-Q[Qt])*(init_L+Qt) if (Qt<0) break;
}
if (Qt<0) puts("Myon");
else{
ans=0;
while (Qt>=0){
if (Rest_Food[Qt]+(n-Q[Qt])*(init_L+Qt)-(Sum[n]-Sum[Q[Qt]])>ans)
ans=Rest_Food[Qt]+(n-Q[Qt])*(init_L+Qt)-(Sum[n]-Sum[Q[Qt]]);
Qt–;
}
printf("%lldn",ans);
}
}
}