社区讨论
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 条回复,欢迎继续交流。
正在加载回复...