NOIP2016普及组初赛部分题解

 输入：1 2 3 4 5 6 0 7

 答案： 6 1 3

这里其实输入到0后while就不执行了，就直接输出答案了，7不会再进行运算，不会输入进去。sum=1+2+3+4+5+6=21,

count=2+1+1+1+1=6

2. 

#include
using namespace std;
int main()
{int i = 100, x=0, y=0;while(i > 0){i--;x = i%8;if(x==1)y++;}cout << y << endl; return 0;} 

答案：13

相当于求解的100以内某个数除以8的余数为1的个数。

1

8*1+1   8*2+1  8*3+1  …… 8*12+1

共有13个数 

3.

#include
using namespace std;
int main()
{int a[6]={1,2,3,4,5,6};int pi = 0;int pj = 5;int t,i;while(pi < pj){t = a[pi];a[pi] = a[pj];a[pj] = t;pi++;pj--;}for(int i = 0; i < 6;i++)cout << a[i] <<",";cout << endl;return 0;} 

 答案：6，5，4，3，2，1，

这个代码实现的就是将数据倒序输出。

这里需要注意最后一个数也要有“，”号。还有缩进的问题，在for循环或者是while循环中，当只有一个语句的时候可以不打{}，也就是说循环不打括号的时候，只有第一个语句在循环语句中。

#include
using namespace std;
int main()
{
    for(int i = 0; i < 4; ++i)
        cout << i << ",";
        cout << "hello";
    return 0;
 } 

与

#include
using namespace std;
int main()
{
    for(int i = 0; i < 4; ++i)
    {
        cout << i << ",";
    }
    cout << "hello";
    return 0;
 } 

等价。

 4.

#include
using namespace std;
int main()
{int i,length1,length2;string s1,s2;s1 ="I have a dream. ";s2 ="I Have a Dream. ";length1 = s1.size();length2 = s2.size();for(int i = 0; i < length1; i++){if(s1[i]>='a' && s1[i] <= 'z')s1[i]-='a'-'A'; }for(int i = 0; i < length1; i++){if(s2[i]>='a' && s2[i] <= 'z')s2[i]-='a'-'A'; }if(s1 == s2) cout << "=" << endl;else if(s1 > s2)cout << ">" << endl;elsecout << "<" << endl;return 0;} 

 答案：=

该代码实现的就是将字符串中的小写字母转换成大写字母，因此最终两个字符串都是“I HAVE A DRAEAM. "

四、完善程序

1.（读入整数）请完善下面的程序，使得程序能够读入两个int范围内的整数，并将这两个整数分别输出，每行一个。

输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。

例如：

输入：

123

-789

输出：

123

-789

#include
using namespace std;
int readint(){int num = 0;//存储读取到的整数int negative = 0;//负数标识char c;//存储当前读取到的字符c = cin.get();while((c < '0' || c>'9') && c!='-')c = ____1____;if(c =='-')negative = 1;else______2____;c = cin.get();while(_____3____){______4____;c = cin.get();}if(negative == 1)_____5_____;return num;
}
int main()
{int a,b;a = readint();b = readint();cout << a << endl << b << endl;return 0;
}

 答案：

（1）cin.get()或者c=getchar()

(2) num = c-'0'或者num=c-48

(3)c >='0'&&c<='9'或者c>=48&&c<=57或isdigit(c)

（4）num = num*10+c-'0'或num=num*10+c-48

(5)num=-num或return -num

#include
using namespace std;
int readint(){int num = 0;int negative = 0;char c;c = cin.get();while((c < '0' || c>'9') && c!='-')//如果是非法读入，就不管它，继续读入 c = cin.get();if(c =='-')//如果读入的是负号，则标记负号，最后按照负数的格式输出 negative = 1;else//如果读入的不是负号，则将字符转成数字格式 num = c-'0';c = cin.get();while(c >= '0' && c <= '9')//如果读入的字符是0~9之间的数 {num = num*10 + c-'0';//将字符转成数字 c = cin.get();}if(negative == 1)//按照负数的格式输出 num = - num;return num;
}
int main()
{int a,b;a = readint();b = readint();cout << a << endl << b << endl;return 0;
}

 2.  （ 郊 游 活 动 ） 有 n 名 同 学 参 加 学 校 组 织 的 郊 游 活 动 ， 己 知 学 校 给 这 n 名 同 学 的 郊 游 总 经 费 为 A 元 ， 与 此 同 时 第 i 位 同 学 自 己 携 带 了 Mi 元 。 为 了 方 便 郊 游 ， 活 动 地 点 提 供 B(>=n ） 辆 自 行 车 供 人 租 用 ， 租 用 第 j 辆 自 行 车 的 价 格 为 Cj元 ， 每 位 同 学 可 以 使 用 自 己 携 带 的 钱 或 者 学 校 的 郊 游 经 费 ， 为 了 方 便 账 务 管 理 ， 每 位 同 学 只 能 为 自 己 租 用 自 行 车 ， 且 不 会 借 钱 给 他 人 ， 他 们 想 知 道 最 多 有 多 少 位 同 学 能 够 租 用 到 自 行 车 。   

本 题 采 用 二 分 法 。 对 于 区 间 [l ， r], 我 们 取 中 间 点 mid 并 判 断 租 用 到 自 行 车 的 人 数 能 否 达 到 mid, 判 断 的 过 程 是 利 用 贪 心 算 法 实 现 的 。

#include
using namespace std;
#define MAXN 1000000
int n,B,A,M[MAXN],C[MAXN],l,r,ans,mid;
bool check(int nn){int count = 0,i,j;i = ____(1)_____;j = 1;while(i <= n){if(___(2)_______)count += C[j]-M[i];i++;j++;}return ____(3)____; 
}void sort(int a[],int l, int r)
{int i=l,j = r,x = a[(l+r)/2],y;while(i <= j){while(a[i] < x) i++;while(a[j] > x) j--;if(i <= j){y = a[i];a[i]=a[j];a[j]=y;i++;j--;} }if(i < r) sort(a,i,r);if(l < j) sort(a,l,j);
}
int main()
{int i;cin >> n >> B >> A;for(i = 1; i <= n; i++)cin >> M[i];for(i = 1; i <= B; i++)cin >> C[i];sort(M,1,n);sort(C,1,B);l = 0;r = n;while(l <= r){mid = (l+r)/2;if(___(4)___){ans = mid;l = mid+1;}elser = __(5)____;}cout << ans << endl; return 0;} 

答案：

先将租用每辆自行车的价格和学生带的钱从小到大排序。

贪心策略：先匹配零花钱带的多的人，判断经费是否超过预算，如果没有超过预算则会有更多的学生可以租用自行车，如果超过了就减少租用自行车的人数。

#include
using namespace std;
#define MAXN 1000000
int n,B,A,M[MAXN],C[MAXN],l,r,ans,mid;
//n个人，B辆车，A总经费，M[i]第i位学生携带的钱，C[i]第i辆车租用的价格 
bool check(int nn){//判断nn个人租车钱是否超过了预算 int count = 0,i,j;i = n-nn+1;//i是排序后钱多的人 j = 1;while(i <= n){if(M[i] < C[j])//如果学生自己带的钱不够，就要用经费 count += C[j]-M[i];//花费的经费 i++;j++;}return count<=A; //花费的经费没超过预算就说明还有人可以租自行车 
}void sort(int a[],int l, int r)//从小到大排序 
{int i=l,j = r,x = a[(l+r)/2],y;while(i <= j){while(a[i] < x) i++;while(a[j] > x) j--;if(i <= j){y = a[i];a[i]=a[j];a[j]=y;i++;j--;} }if(i < r) sort(a,i,r);if(l < j) sort(a,l,j);
}
int main()
{int i;cin >> n >> B >> A;for(i = 1; i <= n; i++)cin >> M[i];for(i = 1; i <= B; i++)cin >> C[i];sort(M,1,n);sort(C,1,B);l = 0;r = n;while(l <= r){mid = (l+r)/2;if(check(mid))//如果没有超过经费，能租车的人数就比mid多 {ans = mid;l = mid+1;}elser = mid -1;}cout << ans << endl; return 0;} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！