网站制作服务平台,crm销售管理系统功能,网站建设意见,wordpress连接自己的域名签订协议
nowcoder 217601
题目大意
给出n个数#xff0c;现在有一个协议书#xff0c;让你从1传到n#xff0c;然后传回1#xff0c;继续传下去 对于第i个数#xff0c;如果前面i-1个数已经匹配过了#xff0c;那么当协议书传过来时即可匹配#xff0c;否则无法匹配…签订协议
nowcoder 217601
题目大意
给出n个数现在有一个协议书让你从1传到n然后传回1继续传下去 对于第i个数如果前面i-1个数已经匹配过了那么当协议书传过来时即可匹配否则无法匹配 我让你让所有数匹配最少传多少圈向上取整
输入样例#1
5
1 5 8 4 3输出样例#1
3输入样例#2
10
11 8 5 7 1 6 2 3 4 10输出样例#2
6样例解释#1
第一轮8 第二轮5 4 3 第三轮1
数据范围
1⩽n⩽8×1051⩽ai⩽1061\leqslant n \leqslant 8 \times 10^5\\1\leqslant a_i\leqslant 10^61⩽n⩽8×1051⩽ai⩽106
解题思路
如果直接暴力枚举会TLE 当匹配完值为iii的点后需要匹配值为i1i1i1的点 那么可以按aia_iai排序这样得到匹配的数的顺序 设viv_ivi为当前数的初始位置 如果vivi−1v_iv_{i-1}vivi−1那么不用多传一圈 否则要多传一圈
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n, ans;
struct node
{int v, s;
}a[800010];
bool cmp(node x, node y)
{return x.s y.s;//按给出的值排序
}
int main()
{scanf(%d, n);for (int i 1; i n; i){scanf(%d, a[i].s);a[i].v i;//记录初始位置}sort(a 1, a 1 n, cmp);//排序for (int i 2; i n; i)if (a[i].v a[i - 1].v)//要多传一圈ans;ans;//不满一圈的printf(%d, ans);return 0;
}
