ZOJ 3963 STL + 贪心

xiaoxiao2021-02-27  223

STL + 贪心

题意:

​ 有n个数字,它们可以再限制条件下可以建树: ai<aj,i<j ,满足ai是aj 的父亲节点,一个父亲节点只能最多连两个儿子,现在要求满足条件下如何建树使得树的数量最少,输出每一个树 的大小和节点。

思路:

​ 这题考察STL和思维能力,若想使得树建的少,那么在插入的节点的时候要寻找比自己小的数字,按照贪心的思想一定要找第一个比自己小的数字,这样才能让后边的节点有更多的机会成为子节点。

​ 用set维护父亲节点,当然必须要是儿子数量不能超过2,超过就删除。当一个节点找不到比自己小的,只能另外再建树即可。

增长见识的地方是:memset里面用sizeof超时!!!利用本身占的字节快。 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <set> using namespace std; const int maxn = 1e5+10; int a[maxn]; struct Node { int anspos; int pos; bool operator <(Node b) const { if(a[pos] == a[b.pos]) return pos < b.pos; return a[pos] < a[b.pos]; } }node; int n; vector<int>ans[maxn]; int num[maxn]; set<Node>s; set<Node>::iterator it; int main() { //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--) { s.clear(); int cnt = 0; scanf("%d",&n); memset(num,0,4*n+4); //memset(num,0,sizeof(num)); for(int i = 1;i <= n; i++) { scanf("%d",&a[i]); node.pos = i; it = s.upper_bound(node); if(it == s.begin()) { node.anspos = cnt; s.insert(node); ans[cnt].push_back(i); cnt++; } else { it--; node = *it; num[node.pos]++; if(num[node.pos] >= 2) { s.erase(it); } node.pos = i; s.insert(node); ans[node.anspos].push_back(i); } } printf("%d\n",cnt); for(int i = 0;i < cnt; i++) { int len = ans[i].size(); printf("%d",len); for(int j = 0;j < len; j++) { printf(" %d",ans[i][j]); } printf("\n"); ans[i].clear(); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-13736.html

最新回复(0)