社区讨论

90分求助

P1094[NOIP 2007 普及组] 纪念品分组参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lus9wh1k
此快照首次捕获于
2024/04/09 19:03
2 年前
此快照最后确认于
2024/04/09 20:36
2 年前
查看原帖
第九个测试点WA了
CPP
/*
排序
cnt分组个数
while 元素有不为0的
{
   for(控制左指针,从前往后)
     for(控制右指针,从后往前)
       有相加等于w的就cnt++,两者数值变成0
   while 存在有数值相加小于w
     for(控制左指针)
       for(右指针)
        有相加小于100就合并两个数值,并到右指针
  for遍历所有
    统计不为0的个数,加进cnt
}
cout  cnt
*/
#include <iostream>
#include <algorithm>
using namespace std;
int num[300100];
int w,n;
bool judgea() { //元素有不为0的
    for(int i = 1; i <= n; i++) {
        if(num[i]!=0) {
            return true;
        }
    }
    return false;
}
bool judgeb() {//存在有数值相加小于w
    for(int l=1; l<n; l++) {
        for(int r=n; r>l; r--) {
            if(num[l]+num[r]<w&&num[l]!=0&&num[r]!=0) { //还有可以合并的
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin>>w>>n;
    for(int i = 1; i <= n; i++) {
        cin>>num[i];
    }
    sort(num,num+n);
    int cnt=0;
    while(judgea()) { //元素有不为0的
        for(int l=1; l<n; l++) {
            for(int r=n; r>l; r--) {
                if(num[l]+num[r]==w) {
                    cnt ++;
                    num[l]=0;
                    num[r]=0;
                }
            }
        }
        while(judgeb()) {  ////存在有数值相加小于w
            for(int l=1; l<n; l++) {
                for(int r=n; r>l; r--) {
                    if(num[l]+num[r]<w&&num[l]!=0&&num[r]!=0) {
                        num[r]=num[r]+num[l];   //合并两个元素
                        num[l]=0;

                    }
                }
            }
        }
        for(int i = 1; i<=n; i++) {
            if(num[i]!=0) {
                num[i]=0;
                cnt++;
            }
        }

    }
    cout<<cnt;
    return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...