百度松果菁英班–oj賽（第三次）

一、小碼哥處理訂單

**題目：**假期快到了，小碼哥在賓館打暑假工。

小碼哥需要處理接下來n天的住房信息，其中第i天賓館有ri個(gè)房間可供租借。共有m份訂單，每份訂單用三個(gè)正整數(shù)描述，分別為dj，sj，tj，表示需要從第sj天到第tj天住房（包括第sj天和第tj天），每天需要出租dj個(gè)房間。

賓館入住是先到先得，也就是說，小碼哥按照訂單給到的先后順序來進(jìn)行處理。如果在分配的過程中遇到一份訂單使從第sj天到第tj天中有至少一天剩余的房間數(shù)量不足dj個(gè)，則需要停止工作，通知當(dāng)前申請(qǐng)人修改訂單。

由于到了假期，賓館入住人數(shù)很多，小碼哥需要知道，是否會(huì)有訂單無法完全滿足。如果有，小碼哥需要通知修改的是哪個(gè)訂單。他真的太累了，請(qǐng)你編程幫小碼哥解決問題。

/**
	輸入格式:第一行包含兩個(gè)正整數(shù)n，m，表示天數(shù)和訂單的數(shù)量;
第二行包含n個(gè)正整數(shù)，其中第i個(gè)數(shù)為ri，表示第i天可用于租借的房間數(shù)量，影響到所有需要在這天租借的訂單;
接下來有m行，表示先后給到的訂單。每行包含三個(gè)正整數(shù)dj，sj，tj，表示租借的數(shù)量，租借開始、結(jié)束分別在第幾天。
每行相鄰的兩個(gè)數(shù)之間均用一個(gè)空格隔開。天數(shù)與訂單均用從1開始的整數(shù)編號(hào)，且申請(qǐng)人編號(hào)范圍為1到m，與訂單號(hào)一樣。
	輸出格式:如果所有訂單均可滿足，則輸出只有一行，包含一個(gè)整數(shù)0，否則(訂單無法完全滿足）輸出兩行，第一行輸出一個(gè)負(fù)整數(shù)-1，第二行輸出需要修改訂單的申請(qǐng)人編號(hào)。
	樣例1   輸入：4 3
                2 5 4 3
                2 1 3
                3 2 4
                4 2 4
			輸出：-1
				2
	備注
對(duì)于100%的數(shù)據(jù)，有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數(shù)組的值全部初始化為0
    memset(sub, 0, sizeof(sub));
    for(int i = 1; i <= num; i++){
        //數(shù)組的差分求值，防止累加到重復(fù)值
        sub[s[i]] += d[i];
        sub[t[i] + 1] -= d[i];
    }
    for(int i = 1; i <= n; i++){
        //前綴和求出每一天至少需要多少個(gè)房間
        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)){//當(dāng)全部訂單均滿足
        cout << 0;
        return 0;
    }
    int mid, ans;
    while(left <= right){
        mid = left + (right - left) / 2;
        //當(dāng)訂單未滿足時(shí)，查找第一天未滿足的訂單
        if(check(mid)){
            right = mid - 1;
            ans = mid;
        }else{//訂單滿足
            left = mid + 1;
        }
    }
    cout << "-1" << endl;
    cout << ans;
    return 0;
}

二、黑手黨

**題目：**有n個(gè)人在玩游戲"黑手黨”，這個(gè)游戲規(guī)則是每局必須有一個(gè)主持，(n -1)名選手。其中第i個(gè)人表示想玩ai局游戲且不當(dāng)主持，請(qǐng)求出滿足每人要求的最少的局?jǐn)?shù)。

/**
	輸入格式:第一行為人數(shù)n ;第二行為數(shù)列a 。
	輸出格式:一行一個(gè)整數(shù)即為答案。
	樣例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){//滿足每個(gè)人要求的最少局?jǐn)?shù)返回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]);//滿足所有人要求的最少場(chǎng)數(shù)
        sum += a[i];//滿足所有人要求的最多場(chǎng)數(shù)
    }
    r = sum;
    while(l <= r){
        mid = l + (r - l) / 2;
        //所有選手的平均場(chǎng)所大于等于最大場(chǎng)數(shù)時(shí)
        if(check(mid)){//此時(shí)局?jǐn)?shù)多了
            r = mid - 1;
            ans = mid;
        }else{//所有選手的平均場(chǎng)所小于等于最大場(chǎng)數(shù)時(shí)，此時(shí)局?jǐn)?shù)少了
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

三、合數(shù)分解

**題目：**給你一個(gè)正整數(shù)n，求最多能分成幾個(gè)合數(shù)。若n為合數(shù)，它自身算一個(gè)合數(shù)。無解輸出-1 。

/**
	輸入格式:第一行一個(gè)正整數(shù)T;接下來T行每行表示一個(gè)測(cè)試數(shù)據(jù)。
	輸出格式:每一行輸出一個(gè)答案。
	樣例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;//不能拆成合數(shù)要做特殊判斷
        //可以被最小的合數(shù)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;//拆分的合數(shù)數(shù)量
        //可以被最小的合數(shù)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;//拆分的合數(shù)數(shù)量
        }
    }
    return 0;
}

四、屠龍勇者

**題目：**很久很久以前，巨龍突然出現(xiàn)，帶來災(zāi)難帶走了公主又消失不見。后來，一名叫做小碼哥的勇者戰(zhàn)勝了巨龍，拯救了王國?，F(xiàn)在，一頭更可怕的多頭噴火龍使王國再次面臨毀滅。巨龍有n個(gè)頭，每個(gè)頭的直徑為di，而國王有m個(gè)勇士，每個(gè)勇士最多只能砍一個(gè)頭，且能力值為 w的勇士只能砍下直徑不超過w的龍頭?，F(xiàn)在請(qǐng)你計(jì)算這些勇士能否消滅這只巨龍。

/**
	輸入格式:輸入共三行，第一行兩個(gè)正整數(shù) n, m 滿足0<n, m ≤1×10^5;第二行n個(gè)正整數(shù)di;第三行m個(gè)正整數(shù)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];
    }
    //核心是間兩個(gè)數(shù)組排序比較即可
    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]){//從后等數(shù)量比較
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

五、數(shù)列分段

**題目：**對(duì)于給定的一個(gè)長(zhǎng)度N的正整數(shù)數(shù)列Ai，現(xiàn)要將其分成連續(xù)的若干段，并且每段和不超過M(可以等于M ），問最少能將其分成多少段使得滿足要求。

/**
	輸入格式:第一行包含兩個(gè)正整數(shù)N，M，表示了數(shù)列Ai的長(zhǎng)度與每段和的最大值;第二行包含N個(gè)空格隔開的正整數(shù)Ai，如題目所述。
	輸出格式:一個(gè)正整數(shù)，輸出最少劃分的段數(shù)。
	樣例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];
        //當(dāng)連續(xù)的值相加小于每段的最大值，則組成一個(gè)段，形成最少段
        if(sum + A[i] <= m){
            sum += A[i];
        }else{//當(dāng)連續(xù)的值相加大于每段的最大值，重新賦予一段
            sum = A[i];
            ans++;
        }
    }
    //由于題目沒有說是否會(huì)有直接大于每段的最大值，做個(gè)簡(jiǎn)單的判斷
    cout << (s > m ? ans : ans + 1);
    return 0;
}

六、小碼哥愛數(shù)字

**題目：**小碼哥很喜歡數(shù)字，有一天他找到老師給他出一道有關(guān)數(shù)字的題目。老師給他一個(gè)位數(shù)很多的正整數(shù)N(不超過250 位)，讓小碼哥去掉其中任意k個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的非負(fù)整數(shù)。小碼哥覺得老師在刁難他（因?yàn)樾〈a哥才一年級(jí)），所以他找身為程序員的你編程對(duì)給定的N和 k ，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。

/**
	輸入格式:N(正整數(shù)，不超過250位)，不必考慮前導(dǎo)0;k(需要?jiǎng)h除的數(shù)字個(gè)數(shù))，保證有輸出，即k小于n的位數(shù)。
	輸出格式:最后剩下的最小數(shù)。
	樣例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--){
        //本題解法主要是求剩下的數(shù)最小，只需從左往右，將當(dāng)前數(shù)大于后面數(shù)刪除即可
        for(int i = 0; i < len; i++){
            if(n[i] > n[i + 1]){//前一個(gè)數(shù)大于后一個(gè)數(shù)，則刪除當(dāng)前數(shù)
                for(int j = i; j <= len; j++){
                    n[j] = n[j + 1];//將后面的數(shù)全部往前挪
                }
                len--;
                break;
            }
        }
    }
    //處理前導(dǎo)0
    while(ld0 < len - 1 && n[ld0] == '0'){
        ld0++;
    }
    for(int i = ld0; i < len; i++){
        cout << n[i];
    }
    return 0;
}

七、潑墨淋漓

**題目：**小碼哥有n幅畫，每幅畫都有一個(gè)編號(hào) ai，編號(hào)為非負(fù)數(shù)且可以相同。他想改變一些畫的編號(hào)，使得n幅畫使用的不同編號(hào)數(shù)量不超過k ( 1<=k<=n <=200000 ) ,問最少需要改變多少幅畫的編號(hào)?

/**
	輸入格式:第一行輸入n，k ;第二行輸入ai 。
	輸出格式:輸出需要改變編號(hào)的畫的最少數(shù)量。
	樣例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];
        //將相同序號(hào)的數(shù)量累加
        b[a[i]] += 1;
    }
    sort(b, b + N, cmp);
    //排完序后從第k個(gè)開始,將后面的數(shù)字相加
    //即是需要改變的編號(hào)數(shù)量
    for(int i = k; i < n; i++){
        ans += b[i];
    }
    cout << ans;
    return 0;
}

八、棧的min

**題目：**小碼哥又被安排任務(wù)了，這次他需要要設(shè)計(jì)一個(gè)堆棧，他除了可以滿足正常的棧的操作以外，還要可以輸出棧內(nèi)最小元素值。

o(n)的算法小碼哥當(dāng)然會(huì)，小碼哥為了給上司一個(gè)驚喜決定設(shè)計(jì)一個(gè)o(1)就能輸出的程序，自然這個(gè)任務(wù)就被丟給你了。

• c(x)-將元素x插入棧中
• y()-移除棧頂元素
• s()-得到棧頂元素
• g_m()-得到棧中最小元素

/**
	輸入格式:第一行輸入操作個(gè)數(shù)n(整數(shù));第2行到第n+1行輸入一個(gè)整數(shù)t分別依次代表上述4種操作;當(dāng)t == 1時(shí)，會(huì)額外輸入一個(gè)整數(shù)x。
	輸出格式:當(dāng)t == 3或t ==4時(shí)，輸出相應(yīng)數(shù)據(jù)，每一行輸出一個(gè)數(shù)據(jù)。
	樣例1   輸入：6
                1 3
                1 4
                3
                4
                2
                3
			輸出：4
                3
                3
	備注
		其中: 1<=t<=4;操作命令總數(shù)[0,100]。
*/         
#include<bits/stdc++.h> 

using namespace std;
stack<int> stackValue;//定義常規(guī)棧
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;
}

九、括號(hào)家族

**題目：**小碼哥在研究只有左括號(hào)和右括號(hào)組成的序列。給出一個(gè)括號(hào)序列，求出最長(zhǎng)合法子串和它的數(shù)量（合法的定義:這個(gè)序列中左右括號(hào)匹配）。

例如: (()不合法，)()(也不合法，但()()和(())合法。

/**
	輸入格式:輸入一行只有左括號(hào)和右括號(hào)組成的序列(只包含小括號(hào))。
	輸出格式:輸出兩個(gè)數(shù)字:最長(zhǎng)子字符串的長(zhǎng)度，以及此類子字符串的數(shù)量，如果沒有這樣的子字符串，則輸出 0 1 。
	樣例1   輸入：()()))()()(()
			輸出：4 2
	備注
    其中:字符串長(zhǎng)度小于等于10^6
*/         
#include<bits/stdc++.h> 

using namespace std;
const int N = 1e6 + 5;
struct NODE{
    char c;//括號(hào)
    int index;//索引
};
bool tag[N];//標(biāo)記位置
string str;
stack<NODE> s;//初始棧

int main(){
    cin >> str;
    int len = str.length();
    for(int i = 0; i < len; i++){
        //如果棧頂元素為( 下一個(gè)想要入棧的為)，則將(出棧，并給兩者標(biāo)記
        if(!s.empty() && s.top().c == '(' && str[i] == ')'){
            tag[i] = true;//標(biāo)記為true，用來后續(xù)查看最長(zhǎng)的子串
            tag[s.top().index] = true;
            s.pop();
        }else{//不符合則間括號(hào)入棧處理
            s.push({
                str[i],
                i
            });
        }
    }

    int maxlen = 0, tmp = 0;
    //等于len是將進(jìn)行最后的最大子串比較
    for(int i = 0; i <= len; i++){//求最大的子串長(zhǎng)度
        if(tag[i]){
            tmp++;//計(jì)算子串的長(zhǎng)度
        }else{
            maxlen = max(maxlen, tmp);//取最大的子串長(zhǎng)度
            tmp = 0;//每次循環(huán)比較結(jié)束重置值
        }
    }

    int count = 0;
    for(int i = 0; i <= len; i++){//求最大子串的數(shù)量
        if(tag[i]){
            tmp++;//計(jì)算子串的長(zhǎng)度
        }else{
            if(tmp == maxlen){
                count++;//當(dāng)子串為最大子串時(shí)，數(shù)量加1
            }
            tmp = 0;//每次循環(huán)比較結(jié)束重置值
        }
    }

    if(maxlen){
        cout << maxlen << " " << count;
    }else{
        cout << "0 1";
    }
    return 0;
}

記錄每一個(gè)學(xué)習(xí)瞬間文章來源地址http://www.zghlxwxcb.cn/news/detail-435664.html

到了這里，關(guān)于百度松果菁英班--oj賽（第三次）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！