sort函式
先簡單介紹一下sort函式
sort對給定區間所有元素進行排序,頭檔案是#include <algorithm>
Sort函式有三個引數：
- 第一個是要排序的陣列的起始地址，
- 第二個是結束的地址（最后一位要排序的地址的下一地址）
- 第三個引數是排序的方法，可以是從大到小也可是從小到大，還可以不寫第三個引數，此時默認的排序方法是從小到大排序，
下面詳細介紹一下sort的各種用法
1.整數陣列直接從小到大排列
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入陣列長度 n
// 然后再輸入n個整數
//輸出
// 從小到大順序輸出陣列
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0;i<n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}2.整數陣列從小到大排序(用cmp)
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入陣列長度 n
// 然后再輸入n個整數
//輸出
// 從小到大順序輸出陣列
int cmp(int x,int y){
return x<y;
}
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
return 0;
}3.整數陣列從大到小排序，這個只需要把2中的cmp的不等號換一下就好了
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入陣列長度 n
// 然后再輸入n個整數
//輸出
// 從大到小順序輸出陣列
int cmp(int x,int y){
return x>y;
}
int main()
{
int i,n,a[200];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n,cmp);
for(i=0;i<n;i++)
printf("%d ",a[i]);
puts("");
return 0;
}4.結構體陣列簡單排序(單屬性)
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入結構體陣列長度 n
// 然后再輸入n個整數，表示結構體的其中的一個屬性q
//輸出
// 根據結構體陣列的屬性q的從大到小順序，輸出結構體陣列
struct s{
int q;
int b;
}a[200];
int cmp(s x,s y)
{
return s.q>y.q
}
int main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i].q);
}
sort(a,a+n,cmp);
for(i=0;i<n;i++)
{
printf("%d 原位置：%d\n",a[i].q,a[i].b);
}
puts(" ");
return 0;
}5.結構體陣列雙屬性排序
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入結構體陣列長度 n
// 然后接下去n行，每行輸入兩個整數，表示結構體的其中的兩個屬性p和q
//輸出
// 根據p屬性的大小進行從大到小排序，在p相等的情況下，則根據q的大小進行從大到小排序
/*
樣例輸入：
5
3 5
4 7
6 3
4 9
3 2
*/
struct s
{
int p;
int q;
}a[200];
int cmp(s x,s y){
if(x.p==y.p)
return x.q>y.q
return x.p>y.p
}
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n,i++)
{
scanf("%d%d",&a[i].p,&a[i].q);
}
sort(a,a+n,cmp);
puts("排序后");
for(i=0;i<n;i++)
{
printf("%d %d\n",a[i].p,a[i].q);
}
puts(" ");
return 0;
}6.結構體陣列雙屬性排序2 // 所有的結構體排序都可以把以上的cmp函式，寫成結構體運算子多載operator<
#include<algorithm>
#include<cstdio>
using namespace std;
//輸入：
// 先輸入結構體陣列長度 n
// 然后接下去n行，每行輸入兩個整數，表示結構體的其中的兩個屬性p和q
//輸出
// 根據p屬性的大小進行從大到小排序，在p相等的情況下，則根據q的大小進行從大到小排序
/*
樣例輸入：
5
3 5
4 7
6 3
4 9
3 2
*/
struct S{
int q;
int p;
bool friend operator <(S a,S b){
if(a.p==b.p) return a.q>b.q;
return a.p>b.p;
}
}a[200];
int main(){
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&a[i].p,&a[i].q);
sort(a,a+n);
puts("排序后:");
for(i=0;i<n;i++)
printf("%d %d\n",a[i].p,a[i].q);
puts("");
return 0;
}7.字串陣列排序（char字串）
#include<cstdio>
#include<sstring>
#include<algorithm>
using namespace std;
//輸入：
// 先輸入字串陣列長度 n
// 然后再輸入n個字串
//輸出
// 從小到大順序輸出字串陣列
char as[200][50];
int cmp(int x,int y)
{
return strcmp(as[x],as[y])==-1;
}
int main()
{
int i,n,a;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",as[i]);
a[i]=i;
}
sort(a,a+n);
for(i=0;i<n;i++)
{
printf("%s\n",as[a[i]]);
}
return 0;
}8.字串陣列排序（string 字串）
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("請輸入要排序的字串:\n");
string s; cin>>s;
sort(s.begin(),s.end());
printf("排序完后的字串為:\n");
cout<<s<<endl;
return 0;
}最優裝載問題
1.給出N個物體，第一個物體重量為W1
2.選擇盡量多的物體，使得總重量不超過C
思路
拿最小的？？
盡量多裝質量小的？？這正確嗎？
假如有這么一種方案是沒有優先裝質量小的，那么我們始終可以
把它換成質量更小的，而數目沒有變化
因此，我們可以確定：我們只需要把所有物體按重量從小到大排序，依次選擇
每個物體，直到放不下為止，就能得到最優解了
雖然證明不是特別嚴謹，要真正證明的話用反證法
下面上代碼:
#include<iostream>
#include<algorithm>
#define MAXN 1000005
using namespace std;
int w[MAXN];//每件古董的重量
int main()
{
int c,n;//c:載重量，n古董數
int sum = 0;//裝入古董的數量
int tmp = 0;//裝入古董的重量
cin >> c >> n;
for(int i= 1; i <= n; ++i)
cin >> w[i];
sort(w+1,w+1+n);
for(int i = 1; i <= n; ++i)
{
tmp += w[i];//這個要在if外面
if(tmp<=c)
sum++;
else
break;
}
cout << sum << endl;
return 0;
}問題二：合并果子
有N堆果子，每堆果子有自己的果子數AI，每次合并可以將任意兩堆果子合并，合并小號的體力
為兩堆果子果子數之和
求消耗的最小體力
1<N<10000
思路：
顯然，選最小的兩堆果子合并N-1次即可
每次加完后可能就不是從小到大了，所以每次加完都要再次排序
#include<bits/stdc++.h>
using namespace std;
long long sum,a[100001],n,d;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
d=n;
sort(a+1,a+n+1);
for(int i=1;i<=d-1;i++)
{
a[1]+=a[2];
for(int j=2;j<=n-1;j++)
a[j]=a[j+1];
sum+=a[1];
n--;
sort(a+1,a+n+1);
// for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
// cout<<" "<<sum<<endl;
}
cout<<sum<<endl;
return 0;
}問題三:國王游戲
恰逢H國國慶，國王邀請n位大臣來玩一個有獎游戲，首先，他讓每個大臣在左右手分別寫下一個整數，
國王自己也在左右手上各寫一個整數，然后，讓這n位大臣排成一排，國王站在隊伍的最前面，排好隊后，
所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的
左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果，國王不希望某一個大臣獲得特別多
的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣所獲得的獎金盡可能少，注意，
國王的位置始終在隊伍的最前面，（金幣數大于1）
【輸入格式】
第一行為一個整數n（1<=n<=1000）表示大臣的人數
第二行為兩個整數a，b（0<a,b<10000），分別表示國王左手和右手上的整數
接下來的n行，每行為兩個整數a，b分別表示每個大臣左手和右手上的整數
【輸出格式】
僅一行為一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數
樣例及解釋
輸入：
3
1 1
2 3
7 4
4 6
輸出：
2
分析
我們可以列舉每一種情況
1 2 3 => 2(獲得獎賞最多的大臣獲得的金幣數)
1 3 2 => 2
2 1 3 => 2
2 3 1 => 9
3 1 2 => 2
3 2 1 => 9
但是列舉顯然不是一個好的做法，因為n挺大，要列舉到死啊，所以顯然有好的做法，我們來分析一下
顯然在交換前面的數時，后面的數答案是沒有變化的，當然對交換的前面的數也沒有影響
也就是說相鄰兩個人位置的交換只會對這兩個人產生影響，我們便從這里為切入點，分析調換相鄰二元組的順序對
答案產生的影響
設這兩個人的位置為i和i+1，左手數字為a[i]和a[i+]，右手數字為b[i]和b[i+1],兩個人的金幣
數為w[i]和w[i+1]，
記p[i]=a[1]*a[2]*...*a[i]
則未調換位置時，k1=w[i]=p[i-1]/b[i]; k2=p[i-1]*a[i]/b[i+1]；
有ans1=max{k1,k2};
調換位置后， k3=p[i-1]/b[i+1]; k4=p[i-1]*a[i+1]/b[i];
有ans2=max{k3,k4};
顯然k1<k4,k3<k2;
如果ans1<ans2,則必有k2<k4 <=> a[i]*b[i]<a[i+1]*b[i+1]
所以為了讓ans取得最小值，我們需要把a[i]*b[i]較小的放在前面，那么我們
以a[i]*b[i]為關鍵字排序即可
同時統計答案時一定不要忘了寫高精度
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int len = 1;//表示高精度資料的長度
int sum[100001] = {0,1};//高精度資料計算結果
struct minister{
ll left;
ll right;
} m[1000001];
bool cmp(minister a,minister b){
return a.left * a.right < b.left * b.right;
}
void multiplicative(ll x){//高精度乘法
for(int i = 1;i <= len; i++){
sum[i] *= x; //各位數乘x,如1111×20 = (1000+100+10+1)×20
}
for(int i = 1;i <= len; i++){
sum[i + 1] += sum[i] / 10;//獲得進位,因為相乘結果可能為 10 3 13 4,需轉化為 1 0 4 3 4
sum[i] %= 10;
}
len++;//因為是sum[i+1],所以肯定會計算到sum[len+1],所以需要len++
while(sum[len] / 10){//觀察最高位是否有進位,因為可能有經過前面的操作后可能有 100 3的情況
sum[len + 1] = sum[len] / 10;
sum[len] %= 10;
len++;
}
//經過前面的一波操作后,最后可能會導致sum[len]的位置上有0,若為0則需要消除
if(sum[len] == 0)
len--;
}
void division(){//高精度除法,這里只需要進行一次操作,所以不需要引數
//思路依舊很簡單,如2345/5=(2000+300+40+5)/5,小學生除法
//->2 3 4 5 ->0 23(3 + 2%5*10) 4 5 -> 0 4 34(4 + 23%5*10) 5 -> 0 4 6 45(5 + 34%5*10)
for(int i = len; i >= 1; i--){
sum[i - 1] += (sum[i] % m[n].right * 10);
sum[i] /= m[n].right;
}
//這波操作必然導致一堆前導0，需消除
while(!sum[len]){
len--;
}
//防止除完了
if(len == 0) cout << "1" << endl;
}
int main(){
cin >> n;
cin >> m[0].left >> m[0].right;
for(int i = 1;i <= n; i++)
cin >> m[i].left >> m[i].right;
sort(m + 1, m + 1 + n, cmp);
for(int i = 0;i < n; i++){
multiplicative(m[i].left);
}
division();
for(int i = len; i >= 1; i--)
cout << sum[i];
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302031.html
標籤：其他