這次我格某人沒有在拖了。這次因?yàn)樯洗蜼50的教訓(xùn)讓我不敢再拖著不寫了，那么開始題吧
目前創(chuàng)新互聯(lián)已為上千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、馬鞍山網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。第一題
輸入 #1
6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12
輸出 #1
1 32
輸入 #2
8 42 24 10 29 27 12 58 31 8 16 26 80 6 25 3 36 11 5 33 20 17 13 15 77 9 4 50 19
輸出 #2
1 77說明/提示
【數(shù)據(jù)范圍】
對(duì)于40%的數(shù)據(jù)有N≤10。
對(duì)于70%的數(shù)據(jù)有N≤18。
對(duì)于100%的數(shù)據(jù)有N≤500。
這題，看看題，感覺需要模擬，但是大致寫了代碼框架，發(fā)現(xiàn)模擬至少要寫三重循環(huán)，而500次，三重循環(huán)，可能會(huì)超時(shí)（雖然不確定）而且還有遞歸，實(shí)現(xiàn)比較復(fù)雜，想想這肯定不是最好的辦法，但是我也想不來最好的辦法，于是只能求助了。
? 這題其實(shí)是個(gè)博弈論問題，諸如此類的問題時(shí)不需要用代碼來模擬實(shí)現(xiàn)游戲的過程的。由于計(jì)算機(jī)總是傾向于破壞最好的組合，所以你肯定是不能拿到最好的組合的。也就是說每組能產(chǎn)生默契值大的組合，一個(gè)人在你這，另一個(gè)人，在計(jì)算機(jī)這，你們都拿不到最好的組合。這時(shí)候你只要拿到每組次大組合中的最佳選項(xiàng)，那么你就是勝券在握了。
再?gòu)某鲱}人的角度出發(fā)，我們做題都是要不擇手段的。如果我們不一定會(huì)贏，那么我們只需要輸出0就可以了，也就是說無腦cout<< 0<< endl;就能騙過一部分的測(cè)試數(shù)據(jù)。如果是某些賽制的比賽，那么就可以得到一部分的得分?？墒聦?shí)上，出題人會(huì)讓你那么好騙數(shù)據(jù)嗎？當(dāng)然不會(huì)，所以，從這個(gè)層面來講，我們?nèi)耸潜刳A的。
? 接著就是上代碼了，貪心算法就是這樣子，題目搞會(huì)了代碼就是輕輕松松簡(jiǎn)簡(jiǎn)單單的。同時(shí)復(fù)習(xí)下外掛函數(shù)sort的使用方法。
重慶分公司
重慶分公司
//三國(guó)游戲
#includeusing namespace std;
const int MAX = 502;
int vec[MAX][MAX] = {0}; //用來存放武將之間的關(guān)系
int n; //用來存放武將的數(shù)目
int main()
{
cin >>n;
for(int i = 1; i<= n; i++)
{
for(int j = i+1; j<= n; j++)
{
cin >>vec[i][j];
vec[j][i] = vec[i][j]; //雙向存儲(chǔ)會(huì)好一些
}
}
int ans = 0;
for(int i = 1; i<= n; i++)
{
sort(vec[i]+1, vec[i]+n+1, greater()); //來排序了，從大到小排序
//從大到小排序的方法第一是greater()
//第二種是用蘭木達(dá)表達(dá)式
//第三種是函數(shù)名字傳參
// for(int j = 1; j<= n; j++)
// {
// cout<< vec[i][j]<< ' ';
// }
ans = max(ans, vec[i][2]);
}
cout<< 1<< endl<< ans;
return 0;
} 
兩個(gè)整數(shù)有一個(gè)空格符分開
輸入輸出樣例輸入 #1
4 2 1 3
輸出 #1
2 4說明/提示
對(duì)于 100%?的數(shù)據(jù)，滿足初始時(shí)，沒有兩個(gè)士兵同在一個(gè)坐標(biāo)，1≤L≤5×10^3，0≤N≤5×10^3，且數(shù)據(jù)保證 N≤L。
? 上一題夠無語(yǔ)了，這題就是更加無語(yǔ)。本來不看題解想著模擬這些人的行動(dòng)真心好復(fù)雜啊，這么多人，每個(gè)人的方向不一樣，這不是關(guān)鍵，關(guān)鍵是，人與人還有碰撞，看到題解的靈魂交換這個(gè)詞恍然大悟，其實(shí)兩個(gè)人相向而行和發(fā)生碰撞后回頭對(duì)于這個(gè)整體來說其實(shí)是等效的，這就是我們靈魂交換的合理之處。也就是說不管是哪個(gè)人，但是我們只要知道有個(gè)人在那個(gè)位置就足夠判斷了。也就是說直接讓人橫穿就行了。知道了這個(gè)之后，代碼就沒那么難了。最長(zhǎng)的情況就是每個(gè)人都往最長(zhǎng)的方向走，取路徑最長(zhǎng)。最短的情況就是每個(gè)人往最短的方向走，取最長(zhǎng)（讓每個(gè)人下橋才行?。?/p>
#includeusing namespace std;
int main()
{
int L; //橋的長(zhǎng)度
cin >>L;
int N; //人的個(gè)數(shù)
cin >>N;
int max_ans = 0, min_ans = 0;
for(int i = 1; i<= N; i++)
{
int X;
cin >>X;
max_ans = max(max_ans, max(X, L+1-X));
min_ans = max(min_ans, min(X, L+1-X));
}
cout<< min_ans<< ' '<< max_ans<< endl;
return 0;
} 
輸入 #1
10 56 12 1 99 1000 234 33 55 99 812
輸出 #1
3 2 7 8 1 4 9 6 10 5 291.90說明/提示
n≤1000,ti?≤10^6，不保證ti??不重復(fù)。
當(dāng) ti??重復(fù)時(shí)，按照輸入順序即可（sort 是可以的）
這個(gè)題是小學(xué)的題，只要優(yōu)先選擇接水時(shí)間短的人來接水就可以完成任務(wù)的。用代碼實(shí)現(xiàn)就可以了。題目的提示說了sort可以，那就sort唄。
注意下每個(gè)人接水的時(shí)間不是自己等待的時(shí)間，第一個(gè)人接水時(shí)n-1個(gè)人在等待。
這題的坑點(diǎn)主要在于當(dāng)用int存儲(chǔ)總時(shí)間時(shí)可能會(huì)越界，而我還沒有看出來（感覺自己退化了）
這時(shí)候要么老老實(shí)實(shí)用double存儲(chǔ)總時(shí)間，要么#define int long long（真的好無恥的做法，盡量別用）double能精確存儲(chǔ)的整數(shù)位數(shù)long long是可以存儲(chǔ)的
#includeusing namespace std;
struct person
{
int num; //編號(hào)
int time; //接水的時(shí)間，注意不是他自己的等待時(shí)間
};
int main()
{
int N;
cin >>N;
vectorarr(N+1); //數(shù)列唄
for(int i = 1; i<= N; i++)
{
int time;
cin >>time;
arr[i].time = time;
arr[i].num = i; //加入這個(gè)人
}
//排序
sort(arr.begin()+1, arr.end(), [](const person &p1, const person &p2)
{
return p1.time< p2.time;
});
double sum = 0;
for(int i = 1; i<= N; i++)
{
if(i != 1)
cout<< ' ';
cout<< arr[i].num;
sum += arr[i].time*(N-i);
}
printf("\n%.2lf\n", sum/N);
} 我們的final boss終于要獻(xiàn)身了，這題的標(biāo)簽最多的，但是選對(duì)外掛也是最簡(jiǎn)單的。
輸入 #1
3 1 2 9
輸出 #1
15說明/提示
對(duì)于 30%?的數(shù)據(jù)，保證有 n≤1000：
對(duì)于 50%?的數(shù)據(jù)，保證有 n≤5000；
對(duì)于全部的數(shù)據(jù)，保證有 n≤10000。
? 這一題最初一眼看來，這不就是哈夫曼樹嗎？于是復(fù)習(xí)了哈夫曼樹后就來做這題，結(jié)果，不出所料，運(yùn)行超時(shí)，，，吃席打臉時(shí)刻?。?！
? 原來還有優(yōu)先隊(duì)列這種玩意啊，不得不說stl的外掛真的是太牛了！
? 下面簡(jiǎn)單介紹下優(yōu)先隊(duì)列，priority_queue，只要#include
? priority_queue
? 就用優(yōu)先隊(duì)列就行，每次從隊(duì)頭拿出兩個(gè)，在隊(duì)尾插進(jìn)一個(gè)，他會(huì)自己排好序的，直到隊(duì)列只有一個(gè)元素為止，這樣子就可以搞定了。把注釋去掉，發(fā)現(xiàn)代碼其實(shí)不長(zhǎng)的，很容易過的。
#includeusing namespace std;
//感覺這題像哈夫曼樹
// struct node
// {
// int value; //當(dāng)前節(jié)點(diǎn)值
// int parent; //雙親結(jié)點(diǎn)
// int lchild; //左孩子
// int rchild; //右孩子
// };
// //選擇，最小的節(jié)點(diǎn)和第二小的節(jié)點(diǎn)
// void select(vectorhftree, int size, int &f1, int &f2)
// {
// int min1 = 0, min2 = 0;
// for(int i = 1; i<= size; i++) //在現(xiàn)今的范圍內(nèi)尋找
// {
// if(hftree[i].value< hftree[min1].value && !hftree[i].parent)
// {
// min1 = i;
// }
// }
// for(int i = 1; i<= size; i++)
// {
// if(hftree[i].value< hftree[min2].value && i != min1 && !hftree[i].parent)
// {
// min2 = i;
// }
// }
// f1 = min1, f2 = min2;
// }
int main()
{
int n;
cin >>n;
// vectorarr(n);
// vectorhftree(2*n); //事實(shí)上節(jié)點(diǎn)數(shù)目只有2*n-1
// hftree[0].value = INT_MAX;
// hftree[0].parent = 0; //頭結(jié)點(diǎn)的初始化，用于比較
// for(int i = 0; i< n; i++)
// {
// cin >>arr[i];
// hftree[i].value = arr[i];
// hftree[i].parent = 0;
// hftree[i].lchild = 0;
// hftree[i].rchild = 0; //先初始化
// }
priority_queue, greater>que; //從小到大的優(yōu)先隊(duì)列
for(int i = 0; i< n; i++)
{
int t;
cin >>t;
que.push(t); //加入t
}
//從n+1開始，在前面尋找
int ans = 0;
// for(int i = n+1; i<= 2*n-1; i++)
// {
// int min1, min2;
// select(hftree, i-1, min1, min2);
// hftree[min1].parent = i; //設(shè)置雙親
// hftree[min2].parent = i; //設(shè)置左右孩子
// hftree[i].lchild = min1;
// hftree[i].rchild = min1;
// hftree[i].value = hftree[min1].value + hftree[min2].value;
// ans += hftree[i].value;
// }
while(que.size() >1)
{
int t1 = que.top(), t2;
que.pop();
t2 = que.top();
que.pop();
que.push(t1+t2);
ans += t1+t2;
}
cout<< ans<< endl;
return 0;
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
