紀念品分組（貪心、排序）-有解無憂

題目來源：https://www.luogu.org/problem/P1094

貪心演算法：先對陣列從小到大排序，用 i = 0, j = n - 1 指標指向首尾元素；如果 a[i] + a[j] ?> w ，則將 a[i]單獨作為一組，指標j-- ；如果 a[i] + a[j] ≤ w，則將 a[i] 和 a[j]? 分為一組，指標 i--, j--，如此重復直到 “取完” 所有元素，

題目描述

元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發放作業，為使得參加晚會的同學所獲得的紀念品價值相對均衡，他要把購來的紀念品根據價格進行分組，但每組最多只能包括兩件紀念品，并且每組紀念品的價格之和不能超過一個給定的整數，為了保證在盡量短的時間內發完所有紀念品，樂樂希望分組的數目最少，

你的任務是寫一個程式，找出所有分組方案中分組數最少的一種，輸出最少的分組數目，

輸入格式

共n+2n+2行:

第11行包括一個整數ww，為每組紀念品價格之和的上上限，

第22行為一個整數nn，表示購來的紀念品的總件數GG，

第33至n+2n+2行每行包含一個正整數P_i(5 \le P_i \le w)Pi?(5≤Pi?≤w)表示所對應紀念品的價格，

輸出格式

一個整數，即最少的分組數目，

輸入輸出樣例

輸入 #1

輸出 #1

說明/提示

50％的資料滿足：1 \le n \le 151≤n≤15

100％的資料滿足：1 \le n \le 30000,80 \le w \le 2001≤n≤30000,80≤w≤200

#include<iostream>
#include<algorithm>
#define N 30000
using namespace std;
int a[N];
bool cmp(int x,int y)//多載sort快排，使其從大到小排序 
{
    return x > y;
}

int main()
{
    int w,n,count = 0;
    cin >> w >> n;
    for(int i = 0;i < n;i++)
        cin >> a[i]; 
    sort(a,a + n,cmp);
//    for(int i = 0;i < n;i++)
//        cout << a[i] << " ";
    int l = 0,r = n - 1;//l為陣列的頭指標，r為陣列的尾指標 
    while(l <= r)//當兩個指標不相遇或剛好相遇時準備結束回圈 
    {
        if(a[l] + a[r] > w)//當最大數加上最小數大于上限值w時，將最大數單獨分為一組，指標后移 
        {
            count++;
            l++;
        }
        else//否則滿足if條件時將頭元素和尾元素放入一組，頭指標后移，尾指標前移 
        {
            count++;
            l++;
            r--;
        }
    }
    cout << count << endl; 
    return 0;
}

/*
100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90
*/

水題不難，最重要的點即為頭指標和尾指標的位置，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/95042.html

標籤：C++

上一篇：劍指offer筆記面試題1----賦值運算子函式

下一篇：C++ Clock函式呼叫及用途