题解

229 条题解

  • 6
    @ 2017-06-28 11:49:45

    不能超过……不是少于

    把数列排序,然后从最大的看,如果没取过的最大的和没取过的最小之和可以放下,就放,要不然就只放没去过的最大的。

    #include<bits/stdc++.h>
    using namespace std;
    int a[100001];
    int main()
    {
        int ans=0,i,j,k=0,l,n,m;
        cin>>m>>n;
        l=n-1;
        for(i=0;i<n;i++) cin>>a[i];
        sort(a,a+n); 
        for(i=0;i<n;) {
            if(a[k]+a[l]<=m) k++,l--,i+=2;
            else l--,i++;
            ans++;
        } 
        cout<<ans<<endl;
        return 0;
    }
    
    
  • 2
    @ 2018-05-27 17:28:55

    sort排序之后就可以用下面这种方法了:
    优先选择最大的物品,如果可以放下一个较小的,放;
    如果无法放下那个较小的物品,放弃放入这个较小的物品。
    贪心思想:在maxk之内使两个物品的w值之和最大
    ```cpp
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int num = 30005;
    int k[num];
    int main() {
    int n,maxk; cin >> maxk >> n;
    for(int i = 0;i < n;i++)
    cin >> k[i];
    sort(k,k + n);
    int temp = 0,x = n - 1;
    int ans = 0;
    while(temp <= x) {
    if(k[x] + k[temp] <= maxk) {
    ans++;
    x--; temp++;
    }
    else {
    ans++; x--;
    }
    }
    cout << ans << endl;
    return 0;
    }

  • 1
    @ 2021-08-29 17:06:50
    #include <bits/stdc++.h>
    using namespace std;
    
    int W,ans=0;
    int n,a[30001];
    int l,r,i;
    int main()
    {
        scanf("%d%d",&W,&n);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        l=1;  r=n;
        while(l<=r)
        {
            if(a[l]+a[r]<=W)   
                l++,r--,ans++;
            else
                r--,ans++;  
        }
        printf("%d",ans);
        return 0;
    }
    
  • 1
    @ 2021-07-02 09:56:22
    a=[]
    def sorta(l,r):
        i=l
        j=r
        mid=a[int((l+r)/2)]
        while i<j:
            while a[i]<mid:
                i=i+1
            while mid<a[j]:
                j=j-1;
            if i<=j:
                tmp=a[i]
                a[i]=a[j]
                a[j]=tmp
                i=i+1
                j=j-1
        if l<j:
            sorta(l,j)
        if i<r:
            sorta(i,r)
    w=int(input())
    def calc(l,r):
        i=l
        j=r
        ans=0
        while i<j:
            ans=ans+1
            if a[i]+a[j]<=w:
                i=i+1
                j=j-1
            elif a[i]<a[j]:
                j=j-1
            else:
                i=i+1
        if i==j:
            ans=ans+1
        return ans
    n=int(input())
    for i in range(0,n):
        a.append(int(input()))
    sorta(0,n-1)
    print(calc(0,n-1))
    
  • 1
    @ 2020-02-07 22:13:10

    排序,如果最大最小之和不超过上限,则为一组。
    否则,最大的自成一组。

    #include<iostream>
    using namespace std;
    int main()
    {
        int max, N, num[30000], group = 0;
        cin >> max >> N;
        int i, j;
        for (i = 0; i < N; i++)cin >> num[i];
        for (i = 0; i < N - 1; i++)for (j = i + 1; j < N; j++)if (num[i] > num[j])
        {
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
        i = 0; j = N - 1;
        while (i <= j) {
            if (num[i] + num[j] <= max) {
                group++;
                i++;
            }
            else group++;
            j--;
        }
        cout << group;
        return 0;
    }
    
  • 1
    @ 2019-12-28 05:17:15

    因为要经常进行头和尾部的操作,所以数据结构选择了deque,两头都能操作的queue。

    #include <iostream>
    #include <deque>
    #include <algorithm>
    using namespace std;
    
    int main(int argc, char *argv[]) {
    #ifdef DEBUG
        freopen("a.in", "r", stdin);
    #endif
        int limit, n, x, r = 0;
        deque<int> l;
        cin >> limit >> n;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            l.push_back(x);
        }
        sort(l.begin(), l.end());
        while (l.size() > 1) {
            r++;
            if (l.back() + l.front() <= limit)
                l.pop_front();
            l.pop_back();
        }
        cout << r + l.size() << endl;
        return 0;
    }
    
    
  • 1
    @ 2019-08-22 21:02:15

    这题看似很难,本质在于 每组数量不超过\(2\)

    显然只需要用\(two\) \(pointers\) ,也就是双指针,尺取法。

    先排序,指针一头一尾。每次看最大的和最小的能不能成一组,不能则 把最大作为一组,尾指针\(---\) ,否则两个一组,尾指针\(--\),头指针\(++\).每次计数。

    贪心策略。

    #include<bits/stdc++.h>
    using namespace std;
    
    int w,n,s=0;
    int l,r,a[30001];
    
    inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
        int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;}
    
    int main(){
        w=read(),n=read(); for(int i=1;i<=n;i++) a[i]=read();
        sort(a+1,a+1+n);
        l=1,r=n;
        while(l<=r){
            if(a[l]+a[r]<=w) l++,r--;
            else r--;
            s++;
        }
        if(l==r) s++;
        printf("%d",s);
        return 0;
    }
    
    
  • 1
    @ 2019-05-26 18:00:34
    #include<bits/stdc++.h>
    using namespace std;
    int W,ans=0;
    int n,a[30001];
    int l,r,i;
    int main()
    {
        scanf("%d%d",&W,&n);
        for(i=1;i<=n;i++)
          scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        l=1;  r=n;
        while(l<=r)
        {
            if(a[l]+a[r]<=W)
              l++,r--,ans++;
            else
              r--,ans++;
        }
        printf("%d",ans);
        return 0;
    }
    
  • 1
    @ 2018-06-15 22:07:59

    水水水......
    直接贴代码吧:
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int a[30005];
    int main()
    {
    int w,n,s=0;
    scanf("%d %d",&w,&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int x=1,y=n;
    while(x<=y)
    {
    if(a[x]+a[y]<=w)
    {
    x++;
    y--;
    s++;
    }
    else
    {
    y--;
    s++;
    }
    }
    printf("%d\n",s);
    return 0;
    }

  • 1
    @ 2018-04-02 23:06:16

    /*
    思路:先按大小排个序,保证开头末尾是最大或最小的,只要循环一遍不会超时
    从最大的开始往回,如果最小的能和它配成一组就配,配不成大的就单独一组
    代码如下
    */
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int a[30001];
    int main()
    {
    int ans=0,n,w;
    scanf("%d",&w);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);//排序
    int min=1,i; //设i变量便于判断是否有最后一个需单独分组,min表示当前最小价值
    for(i=n;i>min;i--) //i从最大的开始,直到匹配到min前
    {
    if((a[i]+a[min])<=w) //如果当前最大加当前最小小于w可分组
    {
    min++;
    ans++;
    // printf("第%d组:%d %d\n",ans,a[i],a[min]);
    continue; //分组成功后跳过本次循环
    }
    ans++; //单独分组
    // printf("第%d组:%d\n",ans,a[i]);
    }
    // printf("%d %d\n",i,min);
    if((min-1)!=i)ans++; //22行里的min++的缘故,这里是min-1而不是min
    printf("%d\n",ans);
    return 0;
    }
    //20 20 30 50 50 60 70 80 90 90
    //1 2 3 4 5

  • 1
    @ 2018-03-23 10:06:48

    这题没啥难度,可能唯一的难点是 不超过max,不是小于max ..

    #include <stdio.h>
    #include <stdlib.h>
    int cmp(const void* a,const void* b){
        return *(int *)b-*(int *)a;
    }
    int main(int argc, char* argv[])
    {
        int max,n,i;
        scanf("%d%d",&max,&n);
        int price[30000];
        for(i=0;i<n;i++)
            scanf("%d",&price[i]);
        qsort(price,n,sizeof(int),cmp);
        int total=0;
        for(i=0;i<n;i++){
            if(price[i]==-1)continue;
            //暴力遍历寻找能与其匹配在一组里的最大值
            int j;
            for(j=i+1;j<n;j++){
                if(price[j]==-1)continue;
                if(price[j]+price[i]<=max){
                    total++;
                    price[j]=price[i]=-1;
                    break;
                }
            }
            if(price[i]!=-1){
                total++;
                price[i]=-1;
            }
        }
        printf("%d",total);
        return 0;
    }
    
    
  • 1
    @ 2017-11-10 10:35:03

    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int n,w;
    int a[30017];
    int cmp(int x,int y)
    {
    return x>y;
    }
    int main()
    {
    cin>>w>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1,cmp);
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
    if(a[i]<=w&&a[i]!=0)
    {
    int p=w-a[i];
    for(int j=i+1;j<=n;j++)
    {
    if(a[j]<=p&&a[j]!=0)
    {
    a[j]=0;
    break;
    }
    }
    cnt++;
    }
    }
    cout<<cnt<<endl;
    return 0;
    }

  • 1
    @ 2017-10-31 21:18:25

    #include <iostream>
    #include<algorithm>
    using namespace std;
    #define size 50001
    int a[size];
    int n,m;
    int main()
    {
    cin>>n>>m; //n是上限 m是个数
    for(int i=1;i<=m;i++)
    {
    cin>>a[i];
    }
    sort(a,a+m+1);
    int sum=0;
    int x=1,y=m; //从"最短的"和"最长的"分头比
    while(x<=y)
    {
    if(x==y) //如果i==j代表他们重合了 这时除了这一个其他的都已经遍历过了 那么加上这一后 结束就行了

    {
    sum++;
    x++;
    y--;
    break;
    }
    if(a[x]+a[y]<=n)
    {
    sum++;
    x++;
    y--;
    }
    else if(a[x]+a[y]>=n) //代表这个短边加上这个长边后会越界 那么就让长边自己一组(j--)但是短边继续等着 和下一个长边比比看

    {
    sum++;
    y--;
    }
    }
    cout<<sum<<endl;
    return 0;
    }

  • 0
    @ 2021-04-24 12:13:11

    include <iostream>

    include <vector>

    include <algorithm>

    using namespace std;
    int solution(vector<int> gift, int line)
    {
    make_heap(gift.begin(), gift.end());
    sort_heap(gift.begin(), gift.end());
    vector<int>::iterator it1=gift.begin(),it2=gift.end()-1;
    int sum = 0;
    while (it1 != it2&&it1<it2)
    {
    if ((*it1) + (*it2) <= line)
    {
    sum++;
    it1++;
    it2--;
    }
    else
    {
    it2--;
    sum++;
    }
    }
    if (it1 == it2)
    sum++;
    return sum;
    }

    int main()
    {
    int Line,n,a;
    vector<int> Gift;
    cin >> Line;
    cin >> n;
    for (int i = 0;i <= n - 1;i++)
    {
    cin >> a;
    Gift.push_back(a);
    }
    cout << solution(Gift, Line);
    return 0;
    }

  • 0
    @ 2020-04-11 17:51:56

    贪心算法

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int w, n;
    int M[30001];
    
    bool cmp(int a, int b)
    {
        return a > b;
    }
    
    int main()
    {
        cin >> w >> n;
        for (int i = 0; i < n; i++)
            cin >> M[i];
        sort(M, M + n, cmp);
        int i, j = n - 1;
        for (i = 0; i <= j; i++)
        {
            int k = M[i];
            while (k + M[j] <= w && i != j)
            {
                k += M[j];
                j--;
            }
        }
        cout << i << endl;
    
        return 0;
    }
    
    
  • 0
    @ 2019-08-02 17:43:56

    python

    items = []
    groups = 0
    
    top_wealth = int(input())
    n = int(input())
    for i in range(0, n):
        items.append(int(input()))
    
    items.sort(reverse=True)
    ###由大到小排序
    
    j = -1
    for i in range(0, n):
    ### i-j=n 时,指针i和指针j指向同一物品
        if i - j == n:  
            groups += 1
            break
        if i - j < n:
            if items[i] + items[j] <= top_wealth:
                groups += 1
                j = j-1
            else:
                groups += 1
    
    print(groups)
    
    
    
    
    
  • 0
    @ 2019-05-05 20:37:41

    #include<iostream>
    #include<queue>
    #include<cmath>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >q1;
    priority_queue<int,vector<int>,less<int> >q2;
    int w,n,ans=0,a,tot;
    int main()
    {
    cin>>w>>n;
    tot=n;
    for(int i=0;i<n;i++)
    {
    cin>>a;
    q1.push(a);
    q2.push(a);
    }
    while(tot>0)
    {
    int s1=0,s2=0,m;
    s1=q1.top();
    q1.pop();
    s2=q2.top();
    q2.pop();
    if(s1+s2>w)
    {
    ans++;
    tot--;
    q1.push(s1);
    }
    else
    {
    ans++;
    tot-=2;
    }
    }
    cout<<ans;
    }

  • 0
    @ 2019-04-07 23:19:04
    //直接AC 爽!
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int w,n; cin>>w>>n;
        int a[n];
        for(int i=0;i<n;++i) cin>>a[i];
        sort(a,a+n);
        int l=0,r=n-1,res=0;
        while(l<=r){
            if(a[r]>w) {++res; --r;}
            else{
                if(a[l]+a[r]>w){
                    ++res; --r;
                }else{
                    ++res; ++l; --r;
                }
            }
        }
        cout<<res;
        return 0;
    }
    
  • 0
    @ 2019-02-16 17:16:12

    水水水,直接贴吧。

    #include<bits/stdc++.h>
    using namespace std;

    int main()
    {
    int w;//w为每组纪念品价格之和的上限
    int n;//n为购买来的纪念品的总和
    cin>>w>>n;
    int a[n];//用于储存n个纪念品的价格
    for(int i=0;i<n;i++){
    cin>>a[i];
    }
    sort(a,a+n);//从小到大排序
    int counter=0;//用于计量当前一组的纪念的价格
    int sum=0;//定义所分的组数
    int mount=0;//定义一组中的礼物的数量
    int x;//作为中间的储存变量
    int index=n;//用于记录还剩余多少个礼品未被分组
    while(index>0){
    int i;
    for(i=n-1;i>=0;i--){//开始循环判断是否大于礼品的金额
    if(a[i]!=0){
    counter=counter+a[i];
    mount++;
    x=a[i];
    a[i]=0;
    }
    if(counter>w){//如果结果大于100则返回原来的状态
    counter=counter-x;
    mount--;
    a[i]=x;
    }
    if(mount==2&&counter<=w){//满足条件的一种退出方式
    index=index-2;
    sum++;
    counter=0;
    mount=0;
    break;
    }
    }
    if(i==-1){//如果到最后还没有合适的则跳出,单独分为一组
    sum++;
    index--;
    counter=0;//把计数器都清零
    mount=0;
    }
    }
    cout<<sum<<endl;//输出结果
    return 0;
    }

  • 0
    @ 2018-10-01 20:42:12
    #include <iostream>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int limit;
        int n;
        cin>>limit>>n;
        int a[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        int residue=n;
        int ans=0;
        for(int i=0,j=n-1;residue>0;)
        {
            if(i==j)
            {
                ans++;
                break;
            }
            else if(a[i]+a[j]<=limit)
            {
                i++;
                j--;
                residue-=2;
                ans++;
            }
            else
            {
                j--;
                residue--;
                ans++;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    

信息

ID
1409
难度
4
分类
贪心 点击显示
标签
递交数
7958
已通过
3119
通过率
39%
被复制
17
上传者