百度松果菁英班–oj赛（第三次）
一、小码哥处理订单
**题目：**假期快到了，小码哥在宾馆打暑假工。
小码哥需要处理接下来n天的住房信息，其中第i天宾馆有ri个房间可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj，sj，tj，表示需要从第sj天到第tj天住房（包括第sj天和第tj天），每天需要出租dj个房间。
宾馆入住是先到先得，也就是说，小码哥按照订单给到的先后顺序来进行处理。如果在分配的过程中遇到一份订单使从第sj天到第tj天中有至少一天剩余的房间数量不足dj个，则需要停止工作，通知当前申请人修改订单。
由于到了假期，宾馆入住人数很多，小码哥需要知道，是否会有订单无法完全满足。如果有，小码哥需要通知修改的是哪个订单。他真的太累了，请你编程帮小码哥解决问题。
/** 输入格式:第一行包含两个正整数n，m，表示天数和订单的数量; 第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的房间数量，影响到所有需要在这天租借的订单; 接下来有m行，表示先后给到的订单。每行包含三个正整数dj，sj，tj，表示租借的数量，租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号，且申请人编号范围为1到m，与订单号一样。 输出格式:如果所有订单均可满足，则输出只有一行，包含一个整数0，否则(订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。 样例1 输入：4 3 2 5 4 3 2 1 3 3 2 4 4 2 4 输出：-1 2 备注 对于100%的数据，有1≤n, m ≤10^6,0≤ri≤10^9,0<dj≤10^9,1≤sj≤tj≤n。 */ #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int n, m, r[N], d[N], s[N], t[N]; bool check(int num){ int sub[N], need[N]; //给sub数组的值全部初始化为0 memset(sub, 0, sizeof(sub)); for(int i = 1; i <= num; i++){ //数组的差分求值，防止累加到重复值 sub[s[i]] += d[i]; sub[t[i] + 1] -= d[i]; } for(int i = 1; i <= n; i++){ //前缀和求出每一天至少需要多少个房间 need[i] = need[i - 1] + sub[i]; //每一天需要的房间和出租房间比较 if(need[i] > r[i]){//不满足出租要求 return true; } } return false; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> r[i]; } for(int i = 1; i <= m; i++){ cin >> d[i] >> s[i] >> t[i]; } int left = 1; int right = m; if(!check(m)){//当全部订单均满足 cout << 0; return 0; } int mid, ans; while(left <= right){ mid = left + (right - left) / 2; //当订单未满足时，查找第一天未满足的订单 if(check(mid)){ right = mid - 1; ans = mid; }else{//订单满足 left = mid + 1; } } cout << "-1" << endl; cout << ans; return 0; }
二、黑手党
**题目：**有n个人在玩游戏"黑手党”，这个游戏规则是每局必须有一个主持，(n -1)名选手。其中第i个人表示想玩ai局游戏且不当主持，请求出满足每人要求的最少的局数。
/** 输入格式:第一行为人数n ;第二行为数列a 。 输出格式:一行一个整数即为答案。 样例1 输入：3 3 2 2 输出：4 备注 其中:3<=n≤ 1e5,1 ≤ai≤ 1e9 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 5; ll a[N], n, l, r, mid, ans, sum; bool check(ll num){//满足每个人要求的最少局数返回true return num * (n - 1) >= sum; } int main(){ cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; l = max(l, a[i]);//满足所有人要求的最少场数 sum += a[i];//满足所有人要求的最多场数 } r = sum; while(l <= r){ mid = l + (r - l) / 2; //所有选手的平均场所大于等于最大场数时 if(check(mid)){//此时局数多了 r = mid - 1; ans = mid; }else{//所有选手的平均场所小于等于最大场数时，此时局数少了 l = mid + 1; } } cout << ans; return 0; }
三、合数分解
**题目：**给你一个正整数n，求最多能分成几个合数。若n为合数，它自身算一个合数。无解输出-1 。
/** 输入格式:第一行一个正整数T;接下来T行每行表示一个测试数据。 输出格式:每一行输出一个答案。 样例1 输入：1 10 输出：2 备注 其中:T≤1e5，1≤n ≤1e9 */ #include<bits/stdc++.h> using namespace std; int t, n; int main(){ cin >> t; while(t--){ cin >> n; if(n == 1 || n == 2 || n == 3 || n == 5 || n == 7 || n == 11){ cout << "-1" << endl;//不能拆成合数要做特殊判断 //可以被最小的合数4取余为0，4 -> 4 8 -> 4+4；取余为2，6 -> 4+2 10 -> 4 + 6 }else if(n % 4 == 0 || n % 4 == 2){ cout << n / 4 << endl;//拆分的合数数量 //可以被最小的合数4取余为1，9 -> 4+4+1=4+5、13 -> 4+4+4+1=4+4+5 }else if(n % 4 == 1 || n % 4 == 3){//取余为15 -> 4+4+4+3=4+4+7 cout << n / 4 - 1 << endl;//拆分的合数数量 } } return 0; }
四、屠龙勇者
**题目：**很久很久以前，巨龙突然出现，带来灾难带走了公主又消失不见。后来，一名叫做小码哥的勇者战胜了巨龙，拯救了王国。现在，一头更可怕的多头喷火龙使王国再次面临毁灭。巨龙有n个头，每个头的直径为di，而国王有m个勇士，每个勇士最多只能砍一个头，且能力值为 w的勇士只能砍下直径不超过w的龙头。现在请你计算这些勇士能否消灭这只巨龙。
/** 输入格式:输入共三行，第一行两个正整数 n, m 满足0<n, m ≤1×10^5;第二行n个正整数di;第三行m个正整数wi，满足0<di, wi≤1 × 10^8。 输出格式:输出共一行，若能消灭输出YES，否则输出NO。 样例1 输入：4 5 6 8 4 10 12 3 9 7 4 输出：YES */ #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, d[N], w[N]; int main(){ cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> d[i]; } for(int i = 1; i <= m; i++){ cin >> w[i]; } //核心是间两个数组排序比较即可 sort(d + 1, d + n + 1); sort(w + 1, w + m + 1); if(n > m){ cout << "NO"; return 0; } for(int i = 1; i <= n; i++){ if(w[i + m - n] < d[i]){//从后等数量比较 cout << "NO"; return 0; } } cout << "YES"; return 0; }
五、数列分段
**题目：**对于给定的一个长度N的正整数数列Ai，现要将其分成连续的若干段，并且每段和不超过M(可以等于M ），问最少能将其分成多少段使得满足要求。
/** 输入格式:第一行包含两个正整数N，M，表示了数列Ai的长度与每段和的最大值;第二行包含N个空格隔开的正整数Ai，如题目所述。 输出格式:一个正整数，输出最少划分的段数。 样例1 输入：5 6 4 2 4 5 1 输出：3 备注 其中: 1≤N ≤10^5,N<M <10^9,1≤ Ai≤109 */ #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int A[N], n, m, ans, s; int main(){ cin >> n >> m; int sum = 0; for(int i = 1; i <= n; i++){ cin >> A[i]; s = A[1]; //当连续的值相加小于每段的最大值，则组成一个段，形成最少段 if(sum + A[i] <= m){ sum += A[i]; }else{//当连续的值相加大于每段的最大值，重新赋予一段 sum = A[i]; ans++; } } //由于题目没有说是否会有直接大于每段的最大值，做个简单的判断 cout << (s > m ? ans : ans + 1); return 0; }
六、小码哥爱数字
**题目：**小码哥很喜欢数字，有一天他找到老师给他出一道有关数字的题目。老师给他一个位数很多的正整数N(不超过250 位)，让小码哥去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。小码哥觉得老师在刁难他（因为小码哥才一年级），所以他找身为程序员的你编程对给定的N和 k ，寻找一种方案使得剩下的数字组成的新数最小。
/** 输入格式:N(正整数，不超过250位)，不必考虑前导0;k(需要删除的数字个数)，保证有输出，即k小于n的位数。 输出格式:最后剩下的最小数。 样例1 输入:175438 4 输出：13 */ #include<bits/stdc++.h> using namespace std; string n; int k, ld0; int main(){ cin >> n; cin >> k; int len = n.length(); while(k--){ //本题解法主要是求剩下的数最小，只需从左往右，将当前数大于后面数删除即可 for(int i = 0; i < len; i++){ if(n[i] > n[i + 1]){//前一个数大于后一个数，则删除当前数 for(int j = i; j <= len; j++){ n[j] = n[j + 1];//将后面的数全部往前挪 } len--; break; } } } //处理前导0 while(ld0 < len - 1 && n[ld0] == '0'){ ld0++; } for(int i = ld0; i < len; i++){ cout << n[i]; } return 0; }
七、泼墨淋漓
**题目：**小码哥有n幅画，每幅画都有一个编号 ai，编号为非负数且可以相同。他想改变一些画的编号，使得n幅画使用的不同编号数量不超过k ( 1<=k<=n <=200000 ) ,问最少需要改变多少幅画的编号?
/** 输入格式:第一行输入n，k ;第二行输入ai 。 输出格式:输出需要改变编号的画的最少数量。 样例1 输入：5 2 1 1 2 2 5 输出：1 */ #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n, k, a[N], b[N], ans; bool cmp(int a, int b){ return a > b;//降序 } int main(){ cin >> n >> k; for(int i = 0; i < n; i++){ cin >> a[i]; //将相同序号的数量累加 b[a[i]] += 1; } sort(b, b + N, cmp); //排完序后从第k个开始,将后面的数字相加 //即是需要改变的编号数量 for(int i = k; i < n; i++){ ans += b[i]; } cout << ans; return 0; }
八、栈的min
**题目：**小码哥又被安排任务了，这次他需要要设计一个堆栈，他除了可以满足正常的栈的操作以外，还要可以输出栈内最小元素值。
o(n)的算法小码哥当然会，小码哥为了给上司一个惊喜决定设计一个o(1)就能输出的程序，自然这个任务就被丢给你了。
c(x)-将元素x插入栈中y()-移除栈顶元素s()-得到栈顶元素
g_m()-得到栈中最小元素
/** 输入格式:第一行输入操作个数n(整数);第2行到第n+1行输入一个整数t分别依次代表上述4种操作;当t == 1时，会额外输入一个整数x。 输出格式:当t == 3或t ==4时，输出相应数据，每一行输出一个数据。 样例1 输入：6 1 3 1 4 3 4 2 3 输出：4 3 3 备注 其中: 1<=t<=4;操作命令总数[0,100]。 */ #include<bits/stdc++.h> using namespace std; stack<int> stackValue;//定义常规栈 stack<int> stackMin;//定义栈求最小元素 void push(int x){//将元素x入栈 stackValue.push(x); if(stackMin.empty() || stackMin.top() >= x){ stackMin.push(x); } } void pop() {//移除栈顶 if(stackMin.top() == stackValue.top()){ stackMin.pop(); } stackValue.pop(); } int top(){//得到栈顶元素 return stackValue.top(); } int getMin(){//得到栈顶元素 return stackMin.top(); } int main(){ int n; cin >> n; while(n--){ int a; cin >> a; switch(a){ case 1: //入栈 int x; cin >> x; push(x); break; case 2: //移除栈顶 pop(); break; case 3: //出栈，得到栈顶元素 cout << top() << endl; break; case 4: //得到栈中的最小元素 cout << getMin() << endl; break; } } return 0; }
九、括号家族
**题目：**小码哥在研究只有左括号和右括号组成的序列。给出一个括号序列，求出最长合法子串和它的数量（合法的定义:这个序列中左右括号匹配）。
例如: (()不合法，)()(也不合法，但()()和(())合法。
/** 输入格式:输入一行只有左括号和右括号组成的序列(只包含小括号)。 输出格式:输出两个数字:最长子字符串的长度，以及此类子字符串的数量，如果没有这样的子字符串，则输出 0 1 。 样例1 输入：()()))()()(() 输出：4 2 备注 其中:字符串长度小于等于10^6 */ #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5; struct NODE{ char c;//括号 int index;//索引 }; bool tag[N];//标记位置 string str; stack<NODE> s;//初始栈 int main(){ cin >> str; int len = str.length(); for(int i = 0; i < len; i++){ //如果栈顶元素为( 下一个想要入栈的为)，则将(出栈，并给两者标记 if(!s.empty() && s.top().c == '(' && str[i] == ')'){ tag[i] = true;//标记为true，用来后续查看最长的子串 tag[s.top().index] = true; s.pop(); }else{//不符合则间括号入栈处理 s.push({ str[i], i }); } } int maxlen = 0, tmp = 0; //等于len是将进行最后的最大子串比较 for(int i = 0; i <= len; i++){//求最大的子串长度 if(tag[i]){ tmp++;//计算子串的长度 }else{ maxlen = max(maxlen, tmp);//取最大的子串长度 tmp = 0;//每次循环比较结束重置值 } } int count = 0; for(int i = 0; i <= len; i++){//求最大子串的数量 if(tag[i]){ tmp++;//计算子串的长度 }else{ if(tmp == maxlen){ count++;//当子串为最大子串时，数量加1 } tmp = 0;//每次循环比较结束重置值 } } if(maxlen){ cout << maxlen << " " << count; }else{ cout << "0 1"; } return 0; }
记录每一个学习瞬间
