首页 > 其他分享 >[luogu1248] 加工生产调度 题解

[luogu1248] 加工生产调度 题解

时间:2024-11-10 17:07:41浏览次数:1  
标签:return luogu1248 题解 调度 hand int peo

考虑 \(i\) 排在 \(j\) 前的条件是 \(a_i+\max(a_j,b_i)+b_j\le a_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为 \(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct hand{
	int a,b,id;
}peo[1005];
int d(hand x){
	if(x.a==x.b) return 0;
	return ((x.a>x.b)?1:-1);
}int cmp(hand x,hand y){
	if(d(x)!=d(y)) return d(x)<d(y);
	if(d(x)>0) return x.b>y.b;
	return x.a<y.a;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>peo[i].a;
	for(int i=1;i<=n;i++)
		cin>>peo[i].b,peo[i].id=i;
	sort(peo+1,peo+n+1,cmp);
	int s=0,c=0;
	for(int i=1;i<=n;i++){
		s+=peo[i].a;
		c=max(c,s)+peo[i].b;
	}cout<<c<<"\n";
	for(int i=1;i<=n;i++)
		cout<<peo[i].id<<" ";
	return 0;
} 

标签:return,luogu1248,题解,调度,hand,int,peo
From: https://www.cnblogs.com/chang-an-22-lyh/p/18538213/luogu1248-jia_gong_sheng_chan_diao_du-t

相关文章

  • CCPC 网络赛题解(D/I/J)
    D根据题目给出的构造方式,\(S_n'\)的长度会达到\(2^n\)数量级,没法求出\(S_n'\),所以考虑递推。设\(dp_{i,l,r}\)为\(S_i'\)里\(T\)的\([l,r]\)区间以子序列的方式出现了多少次,可以写出转移方程:\(dp_{i,l,r}=\sumdp_{i-1,l,k}\cdotdp_{i-1,k+1,r}+[a_i=T_k]\cdot......
  • [JXOI2017] 加法 题解
    最小值最大,考虑二分答案,问题转为判断最小值是否能\(\gex\)。假如\(a_i\gex\),那我们肯定不管;假如\(a_i<x\),那最好能让选择的区间\(r\)值更大,用优先队列维护即可。区间增幅可以用树状数组维护。时间复杂度\(O(n\log^2n)\)。#include<bits/stdc++.h>#defineintlonglon......
  • [CF1981E] Turtle and Intersected Segments 题解
    好题好题。难点在建图,因为图的边数将会决定最小生成树的时间复杂度。我们肯定希望能够只建\(O(n)\)级别的边,这样时间复杂度就可以做到\(O(n\logn)\)。观察到当\(i,j,k\)三个区间能够互相连边时(这里假设\(a_i<a_j<a_k\)),我们绝对不会连\((i,k)\)这条边。那么假如我们将......
  • [CF1981E] Turtle and Intersected Segments 题解
    好题好题。难点在建图,因为图的边数将会决定最小生成树的时间复杂度。我们肯定希望能够只建\(O(n)\)级别的边,这样时间复杂度就可以做到\(O(n\logn)\)。观察到当\(i,j,k\)三个区间能够互相连边时(这里假设\(a_i<a_j<a_k\)),我们绝对不会连\((i,k)\)这条边。那么假如我们将......
  • ABC379E 题解
    ABC379E题解一道很好的题,开始还以为是高精度来着,但是发现不必要也不能用高精度,而是用一种技巧代替。题意Youaregivenastring\(S\)oflength\(N\)consistingofdigitsfrom1through9.Foreachpairofintegers\((i,j)\(1\leqi\leqj\leqN)\),define\(f(......
  • CF2030D QED's Favorite Permutation 题解
    题目传送门前置知识差分解法对于移动,我们可以无脑进行交换来保证移动,然后将中途交换的位置再交换回去。通过手摸不难发现,\(p_{i}\)能移动到\(i\)当且仅当\(s_{\min(i,p_{i})\sim\max(i,p_{i})}\)中不含有LR子串。反向考虑,即LR子串不被上述区间包含,差分判断即可。......
  • 【电力系统优化调度】计及源荷两侧不确定性的含风电电力系统低碳调度(Matlab代码实现)
      ......
  • 题解:[ABC379D] Home Garden
    [ABC379D]HomeGarden题意:开始有一个空集,有\(Q\)次操作,每次有标识数\(op\):若\(op\)为\(1\):为集合添加一个元素\(0\)。若\(op\)为\(2\):输入\(T\),为集合内所有元素增加\(T\)。若\(op\)为\(3\):输入\(H\),删除集合内不小于\(H\)的元素,并输出删除元素个数。......
  • 题解:AT_abc379_e [ABC379E] E - Sum of All Substrings
    很水的一道题。我们先把题目上各地的数字看成一个序列,然后考虑计算该序列分别会对答案的每一位产生多少贡献。具体的,我们从后往前考虑答案的每一位。通过简单推演可知,设你当前考虑到答案的第\(i\)个数字,那么原序列对这一位的贡献为\(\sum_{j=1}^{n-i+1}a_j\timesj\)。这个......
  • 题解:AT_abc379_d [ABC379D] Home Garden
    难度严格小于C题。你考虑每盆花被种植的时间一定单调不降,这启示我们去用二分。具体的,我们用一个数组\(a\)表示当前所有的花的种植时间,并记录一个当前时间\(t\)。对于每个1操作都在数组后面加上个元素\(t\),对于\(2\)操作让\(t\leftarrowt+T\)。对于操作3,能够摘取的......