#LOJ10000. 「一本通 1.1 例 1」活动安排
【题意】
数轴上若干线段，选出最多的线段且它们互不相交。
【思路】
考虑对线段排序。由于要尽可能节约总体右边界，我们以右端点为关键字进行排序，顺序扫描所有区间，如果能将区间加入集合就加入。
也可以考虑对端点离散化后，处理出从每个点开始续一个线段能“跳”到的最近位置，然后模拟跳一下即可。
这里给出后一种思路的代码。
#include <bits/stdc++.h> using namespace std; int s[1005],t[1005],f[2005],n; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>s[i]>>t[i]; map<int,int> mp; for(int i=1;i<=n;i++) { mp[s[i]]++; mp[t[i]]++; } int idx = 0; for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++) it->second = ++idx; for(int i=1;i<=n;i++) { s[i]=mp[s[i]]; t[i]=mp[t[i]]; } for(int i=1;i<=idx;i++) f[i]=idx+1; for(int i=1;i<=n;i++) { f[s[i]]=min(f[s[i]],t[i]); } for(int i=idx-1;i;--i) f[i]=min(f[i],f[i+1]); int pin = 1, cnt = 0; while(pin <= idx) { pin=f[pin]; ++cnt; } cout<<cnt-1<<endl; }
#LOJ10001. 「一本通 1.1 例 2」种树
【题意】
填充一个长度为n的01序列，有h个要求，每个要求描述为(b,e,t)，即下标区间[b,e]中至少有t个1.
【思路】
显然可以差分约束，但可以利用一些性质贪心。
按照右端点排序后依次处理所有区间，同时维护目标01序列，如果当前扫描到的区间不符合要求，则从当前区间的右端点开始向左填充。这样可以保证当前填充进去的新1可以得到最大限度的利用。
本题数据范围较小，直接暴力维护，复杂度O(n^2)。
如果要加速，可以考虑用线段树维护01序列，节点记录区间和与覆盖标记。每次修改时通过在线段树上二分找到一个覆盖边界k，将区间[k,t]覆盖。查询很容易。复杂度O(nlogn).
或者用bitset维护，复杂度O(n^2 / 64)。
#include <bits/stdc++.h> using namespace std; struct range { int l,r,t; bool operator < (const range &b) { return r < b.r; } } a[100005]; int n,h,b[100005],ans=0; int main() { cin>>n>>h; for(int i=1;i<=h;i++) cin>>a[i].l>>a[i].r>>a[i].t; sort(a+1,a+h+1); for(int i=1;i<=h;i++) { int cnt = 0; for(int j=a[i].l;j<=a[i].r;j++) cnt+=b[j]; if(cnt < a[i].t) { cnt = a[i].t - cnt; for(int j=a[i].r;j>=a[i].l && cnt>0; --j) if(b[j]==0) b[j]=1, --cnt, ++ans; } } cout<<ans<<endl; }
#LOJ10002. 「一本通 1.1 例 3」喷水装置
【题意】
L*W的矩形中有n个圆，每个圆心都在宽度方向的中心线上，并知道每个圆的位置与半径。求最少多少个圆可以覆盖整个矩形。
【思路】
考虑对线段排序。由于要尽可能节约总体右边界，我们以右端点为关键字进行排序，顺序扫描所有区间，如果能将区间加入集合就加入。
在这里离散化以后“跳”的思路比较容易出现精度问题而不推荐使用。
#include <bits/stdc++.h> using namespace std; int T,n; double l,w; double x[20005],r[20005]; double pl[20005],pr[20005]; struct Item { double l,r; bool operator < (const Item &x) { return l < x.l; } } item[20005]; int main() { ios::sync_with_stdio(false); cin>>T; while(T--) { cin>>n; cin>>l>>w; memset(x,0,sizeof x); memset(r,0,sizeof r); memset(pl,0,sizeof pl); memset(pr,0,sizeof pr); for(int i=1;i<=n;i++) cin>>x[i]>>r[i]; for(int i=1;i<=n;i++) { double tmp = pow(r[i],2)-pow(w/2.0,2); double del = (tmp>=0? sqrt(tmp) : 0); pl[i] = x[i] - del; pr[i] = x[i] + del; //cout<<pl[i]<<" ,"<<pr[i]<<endl; item[i].l = pl[i]; item[i].r = pr[i]; } sort(item+1,item+n+1); //for(int i=1;i<=n;i++) cout<<item[i].l<<" "<<item[i].r<<endl; double now = 0.0001, tmp = 0.00001; int cnt = 0; for(int i=1;i<=n;i++) { if(now < item[i].l && now < l) { now = tmp; ++cnt;//cout<<"now "<<now<<" "<<cnt<<endl; } tmp = max(tmp, item[i].r); } if(now < l) now=tmp, ++cnt; if(now >= l) cout<<cnt<<endl; else cout<<-1<<endl; } }
#10003. 「一本通 1.1 例 4」加工生产调度
【题意】
有n个产品，每个需要先在A机器加工a[i]时间，再到B机器加工b[i]时间。求怎样使得总时间最短。
【思路】
Johnson双机调度模型。我们可以给出一个简化的proof.
假设只有两个产品。假设先加工1优于先加工2，那么有
a1 + max(b1,a2) + b2 < a2 + max(b2,a1) + b1
化简得到
max(b1,a2) - a2 - b1 < max(b2,a1) - b2 - a1
拆得
-min(b1,a2) < -min(b2,a1)
即
min(a1,b2) < min(a2,b1)
这个结果不可以推广，因为缺乏传递性。我们需要进一步处理
对a,b得大小进行讨论我们发现
1) a1<b1 and a2<b2， 那么我们需要a1<a2排序
2) a1=b1 and a2=b2， 随意
3) a1>b1 and a2>b2， 那么我们需要b2>b1排序
4) a1>b1 and a2<b2， 则不等式一定成立
5) a1<b1 and a2>b2， 则不等式一定不成立
我们很容易发现，一个ai<bi的元素最终会出现在序列的靠前部分，而一个ai>bi的元素最终会出现在序列的靠后部分。即，所有ai>bi的元素一定位于ai<bi的元素之后。
而对于所有ai<bi的元素，我们会按照ai升序排序，对于所有ai>bi的元素，我们会按照bi降序排序。
于是我们得到了Johnson双机调度算法。
我们维护两个栈，将所有元素按min(ai,bi)升序排序后按顺序插入。如果ai<bi就插入第一个，否则插入第二个。最后将第二个栈倒置接在第一个栈后面，得到的就是操作顺序序列。
至于计算序列的时间花费，模拟即可。
#include <bits/stdc++.h> using namespace std; int n; struct Item { int a,b,id; bool operator < (const Item &x) { return min(a,b) < min(x.a,x.b); } } item[100005]; vector <int> ans1,ans2; vector <int> seq; int ta[100005],tb[100005]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>item[i].a, item[i].id=i; for(int i=1;i<=n;i++) cin>>item[i].b; sort(item+1,item+n+1); for(int i=1;i<=n;i++) { if(item[i].a<=item[i].b) ans1.push_back(i); else ans2.push_back(i); } seq.push_back(0); for(int i=0;i<ans1.size();i++) seq.push_back(ans1[i]); for(int i=ans2.size()-1;i>=0;--i) seq.push_back(ans2[i]); for(int i=1;i<=n;i++) ta[seq[i]]=ta[seq[i-1]]+item[seq[i]].a; for(int i=1;i<=n;i++) tb[seq[i]]=max(ta[seq[i]],tb[seq[i-1]])+item[seq[i]].b; cout<<tb[seq[n]]<<endl; for(int i=0;i<ans1.size();i++) cout<<item[ans1[i]].id<<" "; for(int i=ans2.size()-1;i>=0;--i) cout<<item[ans2[i]].id<<(i?" ":""); cout<<endl; }
【拓展】 一类邻项交换排序问题
例1 国王游戏
【题意】
N个人站成一排，每个人有a[i]和b[i]。每个人得到的分数=左边所有人a[i]的乘积 ÷ 自己的b[i]
要求最小化最高得分。
【思路】
考虑相邻的两个人i,j，有j=i+1。我们设i左边所有a[j]的乘积为k。
考虑到调整这两人的顺序不会对前面和后面人的得分造成影响，我们只需要让这两人中得分较高的人的得分尽量小即可。
如果i在前，j在后，则max(k/b[i], (ka[i])/b[j])
如果i在后，j在前，则max(k/b[j], (ka[j])/b[i])
化简得需要交换i,j的充要条件为a[i]b[i] > a[j]b[j]
例2 皇后游戏
【题意】
背景条件同上。设i获得的分数为c[i]，则
i=1时，c[i]=a[i]+b[i]
i>1时，c[i] = max(c[i-1], a[1]+...+a[i]) + b[i]
同样我们要最小化最高得分。
【思路1】
模仿上例化简容易得到min(a[i],b[j]) > min(a[j],b[i])为交换条件。
【严格弱序】
对于一个运算符<，用<表示满足，用!<表示不满足。如果符合以下条件，则为严格弱序。
1) 非自反性 即x !< x
2) 非对称性 即若x<y 则y !< x
3) 传递性 即若x<y,y<z 则x<z
4) 不可比性的传递性 若x!<y y!<x y!<z z!<y 则x!<z z!<y
【对思路1的反思】
很显然对任意i,j,k，若min(ai,bj)<min(aj,bi)且min(aj,bk)<min(ak,bj)那么min(ai,bk)<min(ak,bi)
但不具有不可比性的传递性。由于这里的不可比性可以被看作等号，所以我们很容易找到反例。
这意味着，将若干相邻元素互换后可能会出现前面元素大于后面元素的情况，从而不是最优。
总的来说，一个排序方式如果时正确的，那么它需要满足严格弱序，并且对任意i<j，有min(ai,bj)<=min(aj,bi)
【思路2】
观察到思路1的错误主要出在不可比性上。那么我们可否为不可比性设置一种处理方式来使得取到最优？于是，在min(ai,bj)==min(bi,aj)时，我们将a小的往前放。
【小结】
对于一类可以通过交换相邻两项来使得解非严格变优的问题，我们可以通过邻项交换排序来处理问题。但是需要注意对严格弱序的满足。
#10004. 「一本通 1.1 例 5」智力大冲浪
【题意】
有n个任务，每个任务完成需要1单位时间，每个任务有它的ddl，完成不了则会失去对应的分数。最小化损失。
【思路】
考虑到对于任意的时间段0~t，如果一定要放弃一些，我们一定希望放弃那些损失较小的。
因此将任务按照ddl排序，维护小根堆，枚举当前时间，并加入所有这个时间为ddl的任务。如果小根堆中的元素个数大于当前可以容纳的个数（数值上等于时间），则不断将堆顶弹出。
#include <bits/stdc++.h> using namespace std; struct Item { int s,t; bool operator < (const Item &x) { return t < x.t; } } item[100005]; int n,m; int main() { ios::sync_with_stdio(false); cin>>m>>n; for(int i=1;i<=n;i++) cin>>item[i].t; for(int i=1;i<=n;i++) cin>>item[i].s; sort(item+1,item+n+1); priority_queue <int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++) { q.push(item[i].s); while(q.size() > item[i].t) { m-=q.top(); q.pop(); } } cout<<m<<endl; }
#10005. 「一本通 1.1 练习 1」数列极差
【题意】
给定n个数，每次操作可以删除其中两个数a,b，并插入一个数ab+1。直到只剩下一个数。最后能得到的数中最大的为max最小的为min，求max-min。
【思路】
考虑三个数的情况，如果a<b<c,那么
先操作a,b：{a,b,c} -> {ab+1,c} -> {abc+c+1}
先操作b,c：{a,b,c} -> ... -> {abc+a+1}
归纳可知先处理最小的两个数，最终得到的值最大，反之最小。
于是用一个大根堆和一个小根堆分别维护即可。
#include <bits/stdc++.h> using namespace std; int n,a[100005]; priority_queue <int,vector<int>,greater<int> > q1; priority_queue <int,vector<int>,less<int> > q2; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) q1.push(a[i]), q2.push(a[i]); for(int i=1;i<n;i++) { int t=q1.top(); q1.pop(); t*=q1.top(); q1.pop(); q1.push(t+1); t=q2.top(); q2.pop(); t*=q2.top(); q2.pop(); q2.push(t+1); } cout<<q1.top()-q2.top()<<endl; }
#10006. 「一本通 1.1 练习 2」数列分段
【题意】
长为N的正数列需要分成至少多少段使得每段和不超过M。
【思路】
考虑到第一段一定要从开头开始划。从头开始扫描，必要时候切出一段即可。
#include <bits/stdc++.h> using namespace std; int n,m,a[100005]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; int tmp = 0, ans = 1; for(int i=1;i<=n;i++) { if(tmp+a[i]<=m) { tmp+=a[i]; } else { tmp=a[i]; ans++; } } cout<<ans<<endl; }
#10007. 「一本通 1.1 练习 3」线段
【题意】
数轴上有n线段，选出k个使得没有重合。求k最大值。
【思路】
同10002. 考虑对线段排序。由于要尽可能节约总体右边界，我们以右端点为关键字进行排序，顺序扫描所有区间，如果能将区间加入集合就加入。
#include <bits/stdc++.h> using namespace std; struct Item { int l,r; bool operator < (const Item &x) { return r < x.r; } } item[1000005]; int n; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>item[i].l>>item[i].r; sort(item+1,item+n+1); int pos = 0, ans = 0; for(int i=1;i<=n;i++) { if(item[i].l >= pos) pos = item[i].r, ++ans; } cout<<ans<<endl; }
#10008. 「一本通 1.1 练习 4」家庭作业
同10004.
#include <bits/stdc++.h> using namespace std; int n; struct Item { int a,b; bool operator < (const Item &x) { return a<x.a; } } item[1000005]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>item[i].a>>item[i].b; sort(item+1,item+n+1); priority_queue <int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++) { q.push(item[i].b); while(q.size() > item[i].a) q.pop(); } int ans = 0; while(q.size()) ans+=q.top(), q.pop(); cout<<ans<<endl; }
#10009. 「一本通 1.1 练习 5」钓鱼
【题意】
有n个湖，从i到i+1花时间t[i]。再每个湖花费1个时间可以得分f[i]，再花费一个时间得分f[i]-d[i]，再花费一个f[i]-2d[i]，以此类推。最后可以再任意一个湖结束。求给定总时间内得最大得分。
【题解】
时间范围不是很大，维护一个小根堆为当前所有的选择，从左向右枚举最终在哪个湖结束。由于越向右花在路上的时间越长，能用来钓鱼的时间越少，故每次右移动时弹出堆中的多余元素。每到一个新的湖，将这个湖里所有的选择加入小根堆，同时维护总个数即可。
#include <bits/stdc++.h> using namespace std; int n,h,f[105],d[105],t[105],tmp,ans; priority_queue <int,vector<int>,greater<int> > q; int main() { cin>>n>>h; for(int i=1;i<=n;i++) cin>>f[i]; for(int i=1;i<=n;i++) cin>>d[i]; for(int i=1;i<n;i++) cin>>t[i]; h*=12; for(int i=1;i<=n&&h>0;i++) { for(int j=1;j<=240&&f[i]>0;++j) q.push(f[i]), tmp+=f[i], f[i]-=d[i]; while(q.size()>h) tmp-=q.top(), q.pop(); ans=max(ans,tmp); h-=t[i]; } cout<<ans<<endl; }
#10010. 「一本通 1.1 练习 6」糖果传递
【题意】
环上有n个人，每个人有a[i]个物品。每个人只能向着两侧相邻的人传递，一次代价为1.求所有人的物品个数调整为相同的总代价。
【思路】
记avg = sum(ai)/n，则每个人需要补充的个数为ai - avg
由于引入负数，我们不妨设i像i+1传递的个数为xi，那么
avg = ai - x[i] + x[i-1]
于是x[i]-x[i-1] = ai - avg (i>2)
特别地 i=1时，又avg = a1 - x1 + xn
即x[1]-x[n] = a1 - avg
很容易发现这个关于x[]的方程组又无穷多组解。但是我们可以考虑求解其中的相对关系
不妨将x[1]视作变量，去表示其它
x[2] = ai - avg + x[1] = x[1] - (a[1]-avg)
x[3] = ai - avg + x[2] = a[2] - avg + x[1] + a[1] - avg = x[1] - (a[1]+a[2]-avg-avg)
......
我们现在需要找一个点到所有(sigma(a[1->i])-i*avg)距离和最小。显然是中位数。
#include <bits/stdc++.h> using namespace std; #define ll long long ll n,a[1000005],avg,c[1000005],mid,dis; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) avg+=a[i]; avg/=n; for(int i=1;i<=n;i++) c[i]=c[i-1]+a[i]-avg; sort(c+1,c+n+1); if(n&1) mid = c[n/2+1] * 2; else mid = (c[n/2] + c[n/2+1]); for(int i=1;i<=n;i++) dis+=abs(c[i]*2-mid); dis/=2; cout<<dis<<endl; }