省赛训练 2 3.15
G. The Math of Sailing
题意：
一共有4块布 可以对任意一块布进行裁剪 裁剪后排列 成a1 a2 a3 a4 使得满足
思路：
对上面那个公式进行处理 可以得到 （a1 - 1)(a4 - 1) = (a3 - 1)(a2 - 1) 即 裁剪排列后的布的大小满足前面的公式 将ai-1看成pi 可以确定p1的到小一定最小 p4的大小一定最大 那么就只要把a进行升序排列就能确定 那两个组合了 然后判断 两边式子 的大小 如果 左边 > 右边 就减小 a1使得等式成立 否则 减小a2使得等式成立
为什么一定是减小小的那个才能第一个等式使的左右两边的值最大 ：
设 A = a1 + a2 + a3 + a4 若（a1 - 1)(a4 - 1) < (a3 - 1)(a2 - 1) a1 和 a4 固定不变 a1 + a4 + a2 * a3 = A + (a2 - 1) (a3 - 1) + 1 因为(a2 - 1)(a3 - 1)已经固定 只要使得 a2 + a3最大即可 根据数学 知识就知道要减小最小的那个数 两者的和才会最大
#include#include #include #define ll long long #define FF ios::sync_with_stdio(false),cin.tie(0); using namespace std; const int N = 1e5 + 10; ll n, m, cnt; double b[10]; struct node{ int num; double x; }a[5]; bool comp(node a, node b){ return a.x < b.x; } void solve(){ for(int i = 1; i <= 4; i++){ cin >> a[i].x; a[i].num = i;//记录布的编号和大小 } sort(a + 1, a + 5, comp);//从按布的大小 升序 if(a[1].x == 1) {//如果a[1].x == 1 说明 a[1].x - 1 == 0 那么乘积为 0 a[2].x - 1也一定要是0 ] a[2].x = 1; for(int i = 1; i <= 4; i++){ cout << a[i].num << " \n"[i == 4]; } for(int i = 1; i <= 4; i++){//精度要开的大一点 否则可能过不了 cout << fixed << setprecision(12) << a[i].x << " \n"[i == 4]; } } else{ if((a[1].x - 1) * (a[4].x - 1) < (a[2].x - 1) * (a[3].x - 1)){ a[2].x = ((a[1].x - 1) * (a[4].x - 1)) / (a[3].x - 1) + 1;//较小值变小 } else { a[1].x = ((a[2].x - 1) * (a[3].x - 1)) / (a[4].x - 1) + 1; } for(int i = 1; i <= 4; i++){ cout << a[i].num << " \n"[i == 4]; } for(int i = 1; i <= 4; i++){ cout << fixed << setprecision(12) << a[i].x << " \n"[i == 4]; } } } int main() { FF; cout.setf(ios::fixed); int t = 1; while(t --){ solve(); } return 0; }
D. Exam registration
题意：
给出 n 天想要考试的人数 和 最多可以考试的人数 当想要参加考试的人数多于规定的最大人数时 可以将一个同学移到另一天 要求所有同学中移动次数最多的最小值 如果无法让所有同学都参加考试输出-1
思路:
用二分做 二分答案 即 所有同学中移动最多的同学的最小值 如果满足右边界往左移 否则往左边界往右移 （之前先判断 预约人数是否超过限制人数 如果超过了就直接输出-1）
每次二分查找的时候 可以 初始化aa bb 两个数组 然后 指定一个左边界代表人数没有满的最早的日子 从左到右遍历 优先将左边日子的人数填满 还要控制一下天数的差在 正在查找的 ans的范围内 如果左边界超出n 说明 ans 太小了 左边界要增大 否则继续查找更小的 ans
#include#include #define ll long long #define pi acos(-1) #define FF ios::sync_with_stdio(false), cin.tie(0) using namespace std; const int mod = 1e9 + 7; const int N = 1e6 + 10; const int inf = 0x3f3f3f3f; ll n, m, a[N], b[N], aa[N], bb[N]; ll ans, sum1, sum2; void solve(){ cin >> n; ll ans = inf; for(int i = 1; i <= n; i++){ cin >> a[i]; sum1 += a[i];//计算总预约人数 } for(int i = 1; i <= n; i++){ cin >> b[i]; sum2 += b[i];//计算总限制人数 } if(sum1 > sum2) {如果预约人数比限制人数大 输出-1 cout << "-1\n"; return; } ll l = 0, r = n - 1;//二分答案 while(l <= r){ ll mid = (l + r) / 2; int flag = 1;
//初始化 aa bb 数组 便于后续处理 for(int i = 1; i <= n; i++){ aa[i] = a[i]; bb[i] = b[i]; } int pre = 1;//设置一个左边界
//判断该ans 是否满足要求 for(int i = 1; i <= n; i++){ if(pre + mid < i) pre++;//让左边界再当前i的答案范围内 if(bb[pre] >= aa[i]){//限制人数 > 预约人数 bb[pre] -= aa[i]; if(bb[pre] == 0) pre++;//当天人已满 左边界右移 指向下一天 } else{ while(aa[i]){//当预约人数更多时 if(pre > i + mid || pre > n){//左边界超出答案范围或超出数组大小 都是不满足 flag = 0;//标记一下 跳出 break; } if(aa[i] >= bb[pre]){// aa[i] -= bb[pre]; pre++; } else{ bb[pre] -= aa[i]; aa[i] = 0; } } if(!flag) break; } } if(flag) r = mid - 1;//如果答案满足要求继续查找更小的答案 else l = mid + 1;//如果答案不满足 增大答案值 } cout << l << "\n"; } int main() { FF; int t = 1; while(t --){ solve(); } return 0; }
E. Fair Robbery
题意：
给出 n 个人的财产 对于k 每次可以偷编号为k - n的人的t%的钱 要求投完后这n个人的钱 的最大值和最小值之差 最小 （差最小的前提下如果能偷更多的钱就偷更多）对于每个k（1-n) 求最优的t的值 精度至少1e9
思路：
对于 k = 1 把所有人的钱偷了他们就都一样了 差值为0 t = 1
对于k >= 2
首先 预处理 开个结构体数组 记入每个i 前i 数的最大值和最小值 以及从i开始后缀的最大值和最小值
对于k 如果后缀的最大值 大于前缀的最大值 有两种情况：
- 后缀的最小值小于前缀的最小值 把后缀的最大值变成和前缀的最大值一样 就可以达到最优
- 后缀的最小值比前缀的大 考虑把后缀的最大值变成前缀的最大值 和 把后缀的最小值改成前缀的最小值那个更优
如果 后缀的最大值小于前缀的最大值 也有两种情况 ：
- 后缀的最小值小于前缀的最小值 后缀不能在变 不然最小值也会变小 差值会变大
- 后缀的最小值比前缀的大 后缀怎么改都行因为 最小最大已经固定 那么要求偷得最多 就把后缀的最小值变成前缀的最小值即可
#include#include #define ll long long #define pi acos(-1) #define FF ios::sync_with_stdio(false)// cin.tie(0) using namespace std; const int mod = 1e9 + 7; const int N = 1e6 + 10; const int inf = 0x3f3f3f3f; ll n, m, a[N], b[N], maxx[N], minn[N]; ll ans, sum1, sum2; struct node { ll pmx, pmn, bmx, bmn; }mm[N]; void solve(){ cin >> n;
//预处理记入前缀 最大最小值 for(int i = 1; i <= n; i++){ cin >> a[i]; if(i == 1){ mm[i].pmx = a[i]; mm[i].pmn = a[i]; } else{ mm[i].pmx = max(a[i], mm[i - 1].pmx); mm[i].pmn = min(a[i], mm[i - 1].pmn); } }
//预处理后缀的最大最小值 for(int i = n; i >= 1; i--){ if(i == n){ mm[i].bmx = a[i]; mm[i].bmn = a[i]; } else{ mm[i].bmx = max(a[i], mm[i + 1].bmx); mm[i].bmn = min(a[i], mm[i + 1].bmn); } } for(int i = 1; i <= n; i++){
//k == 1 if(i == 1) cout << fixed << setprecision(12) << 1.0 << " \n"[i == n]; else{ if(mm[i - 1].pmx >= mm[i].bmx && mm[i - 1].pmn <= mm[i].bmn)//情况4 cout << fixed << setprecision(12) << 1 - (double)mm[i - 1].pmn / mm[i].bmn << " \n"[i == n]; else if(mm[i - 1].pmx <= mm[i].bmx && mm[i - 1].pmn >= mm[i].bmn){//情况 1 cout << fixed << setprecision(12) << 1 - mm[i - 1].pmx / (double)mm[i].bmx << " \n"[i == n]; //else cout << fixed << setprecision(12) << 0.0 << " \n"[i == n]; } else if(mm[i].bmx >= mm[i - 1].pmx) {//情况2 double mi = min((double)mm[i - 1].pmn, mm[i].bmn * (mm[i - 1].pmx / (double)mm[i].bmx)); double ma = max((double)mm[i - 1].pmx, mm[i].bmx * (mm[i - 1].pmn / (double)mm[i].bmn)); if(mm[i - 1].pmx - mi < ma - mm[i - 1].pmn) cout << fixed << setprecision(12) << 1 - mm[i - 1].pmx / (double)mm[i].bmx << " \n"[i == n]; else cout << fixed << setprecision(12) << 1 - mm[i - 1].pmn / (double)mm[i].bmn << " \n"[i == n]; }//情况3 else cout << fixed << setprecision(12) << 0.0 << " \n"[i == n]; } } } int main() { FF; cout.setf(ios::fixed); int t = 1; while(t --){ solve(); } return 0; }