社区讨论
90分,还有啥没考虑到吗
P1094[NOIP 2007 普及组] 纪念品分组参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lus9qxux
- 此快照首次捕获于
- 2024/04/09 18:59 2 年前
- 此快照最后确认于
- 2024/04/09 18:59 2 年前
CPP
/*
排序
cnt分组个数
while 元素有不为0的
{
for(控制左指针,从前往后)
for(控制右指针,从后往前)
有相加等于100的就cnt++,两者数值变成0
while 存在有数值相加小于100
for(控制左指针)
for(右指针)
有相加小于100就合并两个数值,并到右指针
for遍历所有
统计不为0的个数,加进cnt
}
cout cnt
*/
#include <iostream>
#include <algorithm>
using namespace std;
int num[300100];
int w,n;
bool judgea() {
for(int i = 1; i <= n; i++) {
if(num[i]!=0) {
return true;
}
}
return false;
}
bool judgeb() {
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()) {
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()) {
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;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...