//区间选点 //数轴上有 n 个闭区间 [a_i, b_i]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个) // //Input //第一行1个整数N(N<=100) //第2~N+1行,每行两个整数a,b(a,b<=100) // INPUT :2 //1 5 //4 6 //OUT PUT:1 #include<bits/stdc++.h> using namespace std; const int N=100010; int n; struct range { int l,r; bool operator<(const range &w)const { return r<w.r; } }ran[N]; int main() { cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; ran[i]={l,r}; } sort(ran,ran+n); int res=0,ed=-2e9; for(int i=0;i<n;i++) if(ed<ran[i].l) { res++; ed=ran[i].r; } cout<<res; return 0; } //区间数组(使用小根堆) //给定N个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。 //输出最小组数。 //输入格式 //第一行包含整数N,表示区间数。 //接下来N行,每行包含两个整数ai,biai,bi,表示一个区间的两个端点。 //输出格式 //输出一个整数,表示最小组数。 //数据范围 //1≤N≤105 //−109 ≤ ai ≤ bi ≤ 109 //输入样例: //3 //-1 1 //2 4 //3 5 //输出样例: //2 #include <iostream> #include <algorithm> #include <queue> 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() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r); sort(range, range + n); // 用小根堆维护所有组的右端点的最大值 // 堆中的每一个值存的是每个组的右端点的最大值 priority_queue<int, vector<int>, greater<int>> heap; for (int i = 0; i < n; i ++ ) { // 如果堆为空或者堆的最小右端点 >= 现在区间的左端点,则说明有交集,不能合并,需要新开一个堆 if (heap.empty() || heap.top() >= range[i].l) heap.push(range[i].r); // 否则说明至少与最小的右端点的组没有交集,将它放到右端点最小的组里去 else { heap.pop(); // 弹出这个区间的最小右端点,插入当前区间的右端点,即将其更新了 heap.push(range[i].r); } } // 输出组的数量 printf("%d\n", heap.size()); return 0; } //合并果子 #include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; priority_queue<int,vector<int>,greater<int> >heap;//构建小根堆 for(int i=0;i<n;i++) { int x; cin>>x; heap.push(x);//将输入的果子数放入到小根堆中,此时最小的果子数会自动排序到上面 } int res=0; while(heap.size()>1)//当堆中的节点数>1时 { int a=heap.top();heap.pop();//取第一个最小的数,然后删除 int b=heap.top();heap.pop();//同理 res+=a+b;//二者相加 heap.push(a+b);//将加完之后的结果存放在小根堆中 } cout<<res<<endl; } //现在各大 oj 上有 n 个比赛,每个比赛的开始、结束的时间点是知道的。 //yyy 认为,参加越多的比赛,noip 就能考的越好(假的)。 //所以,他想知道他最多能参加几个比赛。 //由于 yyy 是蒟蒻,如果要参加一个比赛必须善始善终,而且不能同时参加2 个及以上的比赛。 //输入格式 //第一行是一个整数n ,接下来 n 行每行是2 个整数,表示比赛开始、结束的时间。 // //输出格式 //一个整数最多参加的比赛数目。 // //输入输出样例 //输入 //3 //0 2 //2 4 //1 3 //输出 //2 #include<bits/stdc++.h> #define N 1000005 using namespace std; struct range { int l,r; bool operator<(const range &m)const { return r<m.r; } }ran[N]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; ran[i]={l,r}; } sort(ran,ran+n); int st=ran[0].l,ed=ran[0].r,res=1; for(int i=0;i<n;i++) { if(ran[i].l>=ed) { ed=ran[i].r; res++; } } cout<<res; return 0; } //建立雷达 //http://bailian.openjudge.cn/practice/1328 ///本质还是贪心的区间选点,一开始的思路错了,写了一个小时的代码还是不会做 ///去看题解发现,可以把每个点都变成一个圆,然后在x轴上取交点 ///那么我们是不是可以这样想 ///因为每一个点都需要被覆盖,所以我们需要让每一个点扩充成一个半径是/雷达可以覆盖的半径/的圆 ///然后再把每一个圆与x轴的交点坐标算出来 ///这样我们就成功的把这道题转换成了线段覆盖的问题 ///再把产生的数据按照末尾的结束顺序排序,再在每一个没有访问过的节点的末尾放置一个雷达即可 #include <bits/stdc++.h> using namespace std; struct node { double l,r; }a[1005]; int n,r,num; int cmp(node a, node b) { if(a.r==b.r) return a.l<b.l; return a.r<b.r; } int main() { while(cin>>n>>r) { if(n+r==0) break; int x,y; int f = 0; for(int i=1;i<=n;i++) { cin >>x>>y; if(y>r) f = 1; double d = sqrt(r*r-y*y);///规划成区间 a[i].l=x-d;a[i].r=x+d; } if(f) { printf("Case %d:-1\n",++num); continue; } sort(a+1,a+n+1,cmp); double last=a[1].r; int cnt=1; for(int i=2;i<=n;i++) { if(a[i].l>last) { cnt++; last=a[i].r; } } printf("Case %d:%d\n",++num,cnt); } return 0; } //田忌赛马 //https://blog.csdn.net/weiainibuqi/article/details/106602305?ops_request_misc=&request_id=&biz_id=102&utm_term=%E7%94%B0%E5%BF%8C%E8%B5%9B%E9%A9%AC&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-3-106602305.142^v86^control,239^v2^insert_chatgpt&spm=1018.2226.3001.4187 ///使用磨墨战 ///从大到小排序 #include<bits/stdc++.h> using namespace std; const int N=100010; int n; bool cmp(int a,int b) { return a>b; } int main() { while(cin>>n&&n!=0) { int a[n+1],b[n+1]; int a1=1,b1=1,a2=n,b2=n,res=0; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; sort(a+1,a+1+n,cmp); sort(b+1,b+1+n,cmp); for(int i=1;i<=n;i++) { if(a[a1]>b[b1])///先对比上等马,如果田忌最快的马比王的还快,那就要拿下200; { res+=200; a1++,b1++; } else if(a[a2]>b[b2])///如果没他快,再对比最慢的马 { res+=200; a2--,b2--; } else if(a[a2]<b[b1])///如果两个都拿不下,咱只能用下等马对上等马来干他 ///这里有可能出现两者相等,此时王是最快的马,如果王最快的马等于田忌最慢的马,再和第二个if对比,那就是王就一个马了,不用做文章; { res-=200; a2--; b1++; } } cout<<res<<endl; } return 0; } //小明准备去钓鱼,他准备在一个有 $n$ 个湖的地方钓 $h$ 小时,小明只能按顺序从第 1 个湖 开始,依次在各个湖钓鱼,但是在每个湖的钓鱼时间是由小明自己决定的。 //从第 $i$ 个湖走到第 $i+1$ 个湖的时间是 $t_i$ 个 $5$ 分钟。例如 $t_3 = 4,$ 表明从第 $3$ 个湖走到第 $4$ 个湖需要 $20$ 分钟。 //对于每个湖 $i$ ,在初始的 $5$ 分钟,小明可以钓到 $f_i$ 条鱼,之后每过 $5$ 分钟,可钓到的鱼会 减少 $d_i$, 直到减少为 $0$ 。 //如果当前没有在湖中钓鱼,那么可以钓到的鱼的数量是不变的。 //假设 当前只有小明在钓鱼,请问如果规划钓鱼的安排,使得能钓上的鱼最多? 小明在每个湖的钓鱼时间必须是 $5$ 分钟的倍数。 #include<bits/stdc++.h> using namespace std; const int N=100; struct node { int f,d,num; bool operator<(const node &w)const///重载小于号 { if(f==w.f) return num>w.num;///如果能钓的鱼都相等,那么靠左的湖排在前面 else return f<w.f; } }lake[N]; int n,h,a[N],cnt[N],dist[N]; int main() { while(cin>>n&&n) { memset(dist,0,sizeof dist);///重置两湖之间的距离 memset(a,0,sizeof a); memset(cnt,0,sizeof cnt);///cnt用来记录每个糊钓的次数 int res=-1; cin>>h; h=h*12; for(int i=0;i<n;i++) {cin>>lake[i].f;lake[i].num=i;} for(int i=0;i<n;i++) cin>>lake[i].d; for(int i=1;i<=n-1;i++) {cin>>dist[i];dist[i]+=dist[i-1];}///算出dist priority_queue<node>que; for(int i=0;i<n;i++)///枚举从0-i个湖最大的钓鱼数 { int ans=0; while(!que.empty()) que.pop();///清空队列 memset(a,0,sizeof a); for(int j=0;j<=i;j++) que.push(lake[j]);///入队 int t=h-dist[i];///算出钓鱼用的时间 while(t>0) { node now=que.top(); que.pop(); t--; ans+=now.f; now.f=now.f-now.d; //cout<<a[now.num]<<endl; a[now.num]++; if(now.f<0) now.f=0; que.push(now); } if(ans>res) ///记录当前的最优值以及方案 { res=ans; for(int j=0;j<=i;j++) cnt[j]=a[j]; } } for(int i=0;i<n-1;i++) cout<<cnt[i]*5<<", "; cout<<cnt[n-1]*5<<endl; cout<<"Number of fish expected: "<<res<<endl; cout<<endl; } return 0; }
标签:int,res,++,ran,算法,heap,using,贪心 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17427998.html