多写题解多交流才能学好 oi。
在这里贴了代码,为了看上去完整一些。
大概是一些自己学习的记录罢。
贪心不算客观意义上的算法,感觉还不算一种策略机制。我认为更像一种思路,其内涵就是择优,解题时就去想怎样才能更优。
根据最优的思路能去做很多,如果说贪心是一个题的正解的话太抽象,因此贪心的重点也是在证明。
一般证明可以用反证法。
有时不能验证正确性,也可以适当骗分。
感觉贪心蛮好玩的,挺考察思维能力。
经典题:
1.syoj.1501 最多不相交线段。P1803 凌乱的yyy / 线段覆盖
这个就是找到最多的不相交线段条数。答案是考虑按照右端点从小到大排序,最大限度的向左边缩,不要往右边伸展,然后用这个选定的线段将不符合条件的线段筛掉。即一个点既然能被一条线段覆盖,那就让这条线段尽量的短。
但在 syoj 上会卡奇奇怪怪的东西,输入的时候注意判断一下 l 和 r,右边的不一定比左边大。
#include<bits/stdc++.h> using namespace std; const int N = 5e4 + 10; int n, ans; int vis[N]; struct node{int a, b;} k[N]; bool cmp(node x, node y) { return x.b < y.b; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++ ) { scanf("%d%d", &k[i].a, &k[i].b); if(k[i].b < k[i].a) swap(k[i].a, k[i].b); } sort(k + 1, k + n + 1, cmp); for(int i = 1; i <= n; i ++ ) { if(!vis[i]) { ans ++; vis[i] = 1; for(int j = i + 1; j <= n; j ++ ) { if(k[i].b > k[j].a) vis[j] = 1; } } } printf("%d", ans); return 0; }
2. syoj.1502 区间最少覆盖线段 AcWing 907.区间覆盖
思路和上面那个一模一样吧。按左端点从大到小排序,尽可能的向右延伸。每个点,若有两条线段覆盖,一定找右端点更靠右的那条。
#include<iostream #include<algorithm> using namespace std; const int N=100010; int n; struct Range{ int l,r; bool operator< (const Range &W)const{ return l<W.l;//按左端点排序 } }range[N]; int main(){ int st,ed; scanf("%d%d",&st,&ed);//start end scanf("%d",&n); for(int i=0;i<n;i++){ int l,r; scanf("%d%d",&l,&r); range[i]={l,r}; } sort(range,range+n); int res=0,success=0; for(int i=0;i<n;i++){ int j=i,r=-2e9; while(j<n&&range[j].l<=st){//只要这个区间可以覆盖 r=max(r,range[j].r);//右边的端点最能靠右 j++;//一直往后找区间 } if(r<st){//结果找了一遍都不能覆盖到 res=-1;//那就说明无解 break; } res++; if(r>=ed){//说明找到咧 success=1; break; } st=r; i=j-1;//这之前的都不行就不看了 } if(!success) res=-1; printf("%d",res); }
3.洛谷 P1106 删数问题 传送门
很有趣的有趣题,一开始都容易想假每次删最大的。反例很好找。
在几次尝试后就能发现,每次最优应该删掉该数字的第一个“峰值”。这样找到的数字靠前,影响力大。而对于答案的贡献,因为是一个“峰”,所以其后数字一定比其小,所以删掉后一定最优。
特别注意前导 0。
#include<bits/stdc++.h> using namespace std; const int N = 255; char s[N]; int len, k; int main() { cin >> s >> k; len = strlen(s); while(k -- ) { for(int i = 0; i < len; i ++ ) { if(s[i] > s[i + 1]) { for(int j = i; j < len; j ++ ) s[j] = s[j + 1]; break; } } len --; } int i = 0; while(s[i] == '0' && i < len) i ++; if(i == len) cout << "0"; else for(; i < len; i ++ ) cout << s[i]; }
其他好玩的题还没写捏。
标签:const,int,线段,len,笔记,include,4.24,贪心 From: https://www.cnblogs.com/Moyyer-suiy/p/17350955.html