超级码力在线编程大赛初赛第1场-1-树木规划题解

短命女 2022-12-02 04:16 89阅读 0赞

### 目录 ###

*   *  题目描述
     *  示例
     *   *  输入
         *  输出
     *  说明
     *  分析
     *  代码
     *   *  动规
         *  贪心
     *  其他题目

![在这里插入图片描述][20200829193014544.png_pic_center]

## 题目描述 ##

在一条直的马路上，有n棵树，每棵树有一个坐标，代表它们距离马路起点的距离。 如果每相邻的两棵树之间的间隔不小于d，那么我们认为这些树是美观的。 请计算出最少移除多少棵树，可以让这些树变得美观。  
树木的棵树为n，1<=n<=1e5。 树木的坐标用trees\[\]表示，0<=trees\[i\]<=1e9。最小美观间隔为d，1<=d<=1e9。保证输入的坐标是排好序的，且两两不相同。

## 示例 ##

### 输入 ###

\[1,2,3,5,6\]  
2

### 输出 ###

## 说明 ##

样例中，将位置2与6的树木移走，剩下\[1,3,5\]，它们是美观的。

## 分析 ##

我在一开始把这道题目当作了比较简单的动规。保证相邻两颗树的距离不小于d，这是个很明显的最优子问题结构。  
设dp\[i\]为保留树木i作为最后一棵树木时留下树木的最大数量。遍历所有的j<i，当tree i与tree j的距离不低于d时，更新dp。状态转移方程为：

dp[i]=max(dp[i],dp[j]+1)

后面想到可以用贪心去解决。可以证明：最后一棵树一定可以保留，向前依次取距离满足条件的所有树即可。或是保留第一棵树，之后向后遍历，如果当前的树与上一棵选中的树之间的距离大于等于d，那么就保留这棵树，否则移除。

证明过程为：假设最终的最优解不可以包括最后一棵树，那么假设最优解中最后一棵树为I(n)，倒数第二棵树为I(n-1)。则有trees\[I(n)\]-trees\[I(n-1)\]>=d。由于最后一棵树j一定满足trees\[j\]>trees\[I(n)\]，因此一定有trees\[j\]-trees\[I(n-1)\]>d。所以不选择树I(n)，而是选择j是完全可以的，因此**保留最后一棵树一定可以得到最优解**。以此类推，每次选择当前满足条件的最后面一棵树，问题解决。

显然动规算法的时间复杂度为O(N^2)，贪心算法的时间复杂度为O(N)。

## 代码 ##

### 动规 ###

#include <vector>
    #include <iostream>
    using namespace std;
    class Solution { 
    	public:
    		int treePlanning(vector<int> &trees, int d) { 
    			// write your code here.
    			int dp[trees.size()];
    			for(int i=0; i<trees.size(); i++)
    				dp[i]=1;
    			for(int i=1; i<trees.size(); i++) { 
    				for(int j=0; j<i&&trees[i]-trees[j]>=d; j++) { 
    					dp[i]=max(dp[i],dp[j]+1);
    				}
    			}
    			int max=0;
    			for(int i=0; i<trees.size(); i++){ 
    				cout<<dp[i]<<" ";
    				if(dp[i]>max)
    					max=dp[i];
    			}
    			return trees.size()-max;
    		}
    };
    int main() { 
    	vector<int> v;
    	v.push_back(0);
    	v.push_back(2);
    	v.push_back(3);
    	v.push_back(5);
    	v.push_back(6);
    	v.push_back(9);
    	v.push_back(10);
    	v.push_back(13);
    	v.push_back(14);
    	v.push_back(15);
    	Solution s;
    	cout<<endl<<s.treePlanning(v,2);
    	return 0;
    }

### 贪心 ###

class Solution { 
    	public:
    		int treePlanning(vector<int> &trees, int d) { 
    			// write your code here.
    			int count=1;
    			int curr=trees.size()-1;
    			while(1) { 
    				int j=curr-1;
    				while(j>=0&&trees[curr]-trees[j]<d) { 
    					j--;
    				}
    				if(j<0)
    					break;
    				if(trees[curr]-trees[j]>=d)
    					curr=j;
    				count++;
    			}
    			return trees.size()-count;
    		}
    };

## 其他题目 ##

[超级码力在线编程大赛初赛第1场-2-正三角形拼接题解][1_-2-]

[超级码力在线编程大赛初赛第1场-4-对称前后缀题解][1_-4-]

三道题目AC，喜提阿里t恤一件~

[20200829193014544.png_pic_center]: /images/20221123/6998e1fd2675453d9efa8218b5b57f20.png
[1_-2-]: https://blog.csdn.net/qq_41112170/article/details/108298745
[1_-4-]: https://blog.csdn.net/qq_41112170/article/details/108309953